拓扑排序(队列实现)

什么是拓扑排序呢？就是将一个有向无环图中所有顶点在不违反先决条件关系的前提下排成线性序列的过程称为拓扑排序。
学拓扑排序有什么用呢？当然有用啦~。比如说学校排课的时候，会考虑到有的课程需要先修。我们学完C程序设计这门课，有了编程基础，然后才能学习数据结构。大学要修很多门课程的，人为的去排课很头痛的，这时候就可以用拓扑排序解决这个问题。
拓扑排序只针对有向无环图(DAG)，有两种方法可以实现，一种是队列实现，另外一种是深搜(DFS)实现。
这里先介绍队列实现的方法。
（1）从图中选择任意一个入度为0的顶点且输出
（2）从图中删掉此顶点及所有的出边，将其入度减少1
（3）回到第（1）步继续执行

我们对上面图进行拓扑排序，我这里采用的是邻接表储存图，贴代码。

#include<vector>
#include<iostream>
#include<queue>
using namespace std;
class Graph
{
	int v;                             //顶点个数
	vector<int> *adj;                   //邻接表
	int *indegree;                      //每个顶点的入度
public:
	Graph(int n);                       //构造函数
	~Graph();                           //析构函数
	void addEdge(int start,int end);    //添加边
	void TopsortbyQueue();              //拓扑排序
};

Graph::Graph(int n)
{
	v=n;
	adj=new vector<int>[n];    
	indegree=new int[n];
	for(int i=0;i<n;i++)             //入度初始化为0
		indegree[i]=0;
}
Graph::~Graph()
{
	delete [] adj;
	delete [] indegree;
}
void Graph::addEdge(int s,int e)
{
	adj[s].push_back(e);
	indegree[e]++;                      //入度加1
}

void Graph::TopsortbyQueue()
{
	queue<int> aqueue;                   //使用STL的队列
	int count = 0;                       //记录遍历顶点的个数
	for(int i=0;i<v;i++)
	{
		if(indegree[i]==0)               //将入度为0的顶点入队
			aqueue.push(i);
	}

	while(!aqueue.empty())				 //如果队列不空
	{
		int node = aqueue.front();       //获得队列顶部元素
		aqueue.pop();                    //队列出队
		cout<<node<<" ";                 //输出
		count++;                         //遍历到的顶点个数加1
		for(vector<int>::iterator ii=adj[node].begin();ii!=adj[node].end();ii++)
		{
			indegree[*ii]--;                              //相邻的顶点入度减1
			if(indegree[*ii]==0)                          //顶点入读减为0则入队
				aqueue.push(*ii);
		}
	}

	if(count<v)                                  //如果没有遍历全部节点说明图中有环
		cout<<"有环"<<endl;

}

int main()
{
	Graph g(9);
	g.addEdge(0,2);
	g.addEdge(0,7);
	g.addEdge(1,2);
	g.addEdge(1,4);
	g.addEdge(1,3);
	g.addEdge(2,3);
	g.addEdge(3,5);
	g.addEdge(3,6);
	g.addEdge(4,5);
	g.addEdge(7,8);
	g.addEdge(8,6);
	g.TopsortbyQueue();
	return 0;
}

运行结果

图的每条边处理一次，图的每个顶点访问一次，采用邻接表表示时时间复杂度为 O(n+e)。采用相邻矩阵表示时，为O(n*n)。
对DFS实现拓扑排序有兴趣的，点击：拓扑排序DFS版