频道栏目
首页 > 程序开发 > 软件开发 > Java > 正文
数据结构:图--拓扑排序
2014-08-03 11:17:40         来源:自由人的自由结合  
收藏   我要投稿

拓扑排序

拓扑排序

在实际应用中,有向图的边可以看做是顶点之间制约关系的描述。把顶点看作是一个个任务,则对于有向边表明任务Vj的完成需等到任务Vi完成之后,也就是说任务Vi先于任务Vj完成。对于一个有向图,找出一个顶点序列,且序列满足:若顶点Vi和Vj之间有一条边,则在此序列中顶点Vi必在顶点Vj之前。这样的一个序列就称为有向图的拓扑序列(topological order)。

步骤

 

从有向图中选取一个没有前驱(入度为0)的顶点输出。删除图中所有以它为起点的弧。 重复上述两个步骤,此时会出现两种情形 1.所有顶点都已输出,输出序列就是拓扑序列。 2.已没有无前驱的顶点,但任然有顶点没有输出,这表明该有向图是有环的。 可见拓扑排序可以检测有向图是否有环。 必须指出,即使是存储结构已确定,拓扑序列也不一定是唯一的。拓扑排序序列不仅跟存储结构有关也与具体采用的算法有关。

代码

类定义
#include  
#include
#include
using namespace std;
/*
用邻接矩阵实现图  
拓扑排序必须是有向图
*/
class Graph
{
private:
	//顶点数  
	int numV;
	//边数  
	int numE;
	//顶点的入度
	int *indegree;
	//邻接矩阵  
	int **matrix;
public:
	/*
	构造方法
	numV是顶点数,isWeighted是否带权值,isDirected是否有方向
	*/
	Graph(int numV);
	//建图  
	void createGraph(int numE);
	//析构方法  
	~Graph();
	//获取顶点数  
	int getVerNums()
	{
		return numV;
	}
	//获取边数  
	int getEdgeNums()
	{
		return numE;
	}
	//拓扑排序
	void topologicalSort();
	//打印邻接矩阵  
	void printAdjacentMatrix();
	//检查输入  
	bool check(int, int);
};
类实现
//构造函数,指定顶点数目
Graph::Graph(int numV)
{
	//对输入的顶点数进行检测
	while (numV <= 0)
	{
		cout << 顶点数有误!重新输入 ;
		cin >> numV;
	}
	this->numV = numV;
	//构建邻接矩阵,并初始化
	matrix = new int*[numV];
	int i, j;
	for (i = 0; i < numV; i++)
		matrix[i] = new int[numV];
	//由于权值对于拓扑排序并无作用,故采取无权图的做法
	for (i = 0; i < numV; i++)
	for (j = 0; j < numV; j++)
		matrix[i][j] = 0;
	//构建顶点的入度数组,并初始化
	indegree = new int[numV];
	for (i = 0; i < numV; i++)
		indegree[i] = 0;
}
void Graph::createGraph(int numE)
{
	/*
	对输入的边数做检测
	一个numV个顶点的有向图,最多有numV*(numV - 1)条边
	*/
	while (numE < 0 || numE > numV*(numV - 1))
	{
		cout << 边数有问题!重新输入 ;
		cin >> numE;
	}
	this->numE = numE;
	int tail, head, i;
	i = 0;
	cout << 输入每条边的起点(弧尾)、终点(弧头) << endl;
	while (i < numE)
	{
		cin >> tail >> head;
		while (!check(tail, head))
		{
			cout << 输入的边不正确!请重新输入  << endl;
			cin >> tail >> head;
		}
		matrix[tail][head] = 1;
		indegree[head]++;
		i++;
	}
}
Graph::~Graph()
{
	int i;
	for (i = 0; i < numV; i++)
		delete[] matrix[i];
	delete[]matrix;
	delete[]indegree;
}
//拓扑排序
void Graph::topologicalSort()
{
	int i, vertex;
	queue q;
	//入度为零的顶点入队
	for (i = 0; i < numV; i++)
	if (indegree[i] == 0)
		q.push(i);
	bool *visited = new bool[numV];
	for (i = 0; i < numV; i++)
		visited[i] = false;
	while (!q.empty())
	{
		vertex = q.front();
		q.pop();
		cout << setw(4) << vertex;
		visited[vertex] = true;
		for (i = 0; i < numV; i++)
		if (matrix[vertex][i] == 1)
		{
			//调整入度,入度为0则需入队
			if (!(--indegree[i]))
				q.push(i);
		}
	}
	cout << endl;
	for (i = 0; i < numV; i++)
	if (!visited[i])
		cout << 该有向图有环!;
	cout << endl;
	delete[]visited;
}
//打印邻接矩阵  
void Graph::printAdjacentMatrix()
{
	int i, j;
	cout.setf(ios::left);
	cout << setw(4) <<  ;
	for (i = 0; i < numV; i++)
		cout << setw(4) << i;
	cout << endl;
	for (i = 0; i < numV; i++)
	{
		cout << setw(4) << i;
		for (j = 0; j < numV; j++)
			cout << setw(4) << matrix[i][j];
		cout << endl;
	}
}
bool Graph::check(int tail, int head)
{
	if (tail < 0 || tail >= numV || head < 0 || head >= numV)
		return false;
	return true;
}
主函数
int main()
{
	cout << ******拓扑排序***by David*** << endl;
	int numV, numE;
	cout << 建图... << endl;
	cout << 输入顶点数 ;
	cin >> numV;
	Graph graph(numV);
	cout << 输入边数 ;
	cin >> numE;
	graph.createGraph(numE);
	cout << 打印邻接矩阵... << endl;
	graph.printAdjacentMatrix();
	cout << 拓扑排序...<

运行

\\ 完整代码下载:拓扑排序 若有所帮助,顶一个哦! 专栏目录:数据结构与算法目录

 

点击复制链接 与好友分享!回本站首页
相关TAG标签 拓扑 数据结构
上一篇:Struts2体系结构与基本流程
下一篇:一串数字中有两个只出现一次的数字其余都是成对相同,求这两个数
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站