有向无环图的拓扑排序

参考博客http://blog.csdn.net/lrgdongnan/article/details/51679781

http://www.cnblogs.com/en-heng/p/5085690.html

有向无环图（Directed Acyclic Graph, DAG）是有向图的一种，字面意思的理解就是图中没有环。常常被用来表示事件之间的驱动依赖关系，管理任务之间的调度。拓扑排序是对DAG的顶点进行排序，使得对每一条有向边(u, v)，均有u（在排序记录中）比v先出现。亦可理解为对某点v而言，只有当v的所有源点均出现了，v才能出现。

1.算法原理与实现：

（1）入度表

对于DAG的拓扑排序，显而易见的办法：

• 找出图中0入度的顶点；
• 依次在图中删除这些顶点，删除后再找出0入度的顶点；
• 然后再删除……再找出……
• 直至删除所有顶点，即完成拓扑排序

为了保存0入度的顶点，我们采用数据结构栈（亦可用队列）

#include<iostream>
#include<stack>
#include<vector>
#include<list>
using namespace std;

vector<list<int>> Adj;//邻接表
vector<int> inDegree;//保存每个节点的入度
stack<int> stk; //保存当前入度为0的节点编号

void CreateGraph()
{
	int n, m, v1, v2;
	cin >> n >> m;
	Adj.assign(n, list<int>());
	inDegree.assign(n, 0);

	while (m--)
	{
		cin >> v1 >> v2;
		Adj[v1].push_back(v2);
		inDegree[v2]++;
	}
	for (int i = 0; i < n;i++)
	if (inDegree[i] == 0)stk.push(i);


}

void tpSort()
{
	vector<int> vec;
	int v;
	while (!stk.empty())
	{
		v = stk.top();
		stk.pop();
		//遍历与节点v相邻的节点
		for (auto it = Adj[v].begin(); it != Adj[v].end(); it++)
		{
			inDegree[*it]--;
			if (inDegree[*it] == 0)stk.push(*it);
		}
		vec.push_back(v);
	}

	if (vec.size() != inDegree.size())
	{
		cout << "图中存在环路，不能进行拓扑排序\n";
		return ;
	}

	for (auto item : vec)
		cout << item << " ";
	cout << endl;

}

int main()
{
	CreateGraph();
	tpSort();
	system("pause");
	return 0;

}

（2）DFS

核心思想是当当前的点被加入栈之前，要保证它的所有邻接顶点都已经加入到栈中了，这样栈中有顶自下的顺序就是入度从小到大的顺序。

//基于DFS的拓扑排序
#include<iostream>
#include<stack>
#include<list>

using namespace std;

class Graph{
private:
	int V;            //顶点数量
 	list<int> *adj;   //邻接链表
	//采用DFS的思想，根据递归过程，很容易看出入度为0的点是最后被加入到栈中的。  
	//因为只有该点的所有邻接点都加入到栈之后，这个点才会被加入到栈   
	void toplogicalSortUtil(int v, bool visit[], stack<int>& s)
	{
		visit[v] = true;
		list<int>::iterator itr;
		//对该点的所有邻接点进行拓扑排序 
		for ( itr = adj[v].begin(); itr != adj[v].end(); itr++)
		{
			bool kk = !visit[*itr];
				if (kk)
				toplogicalSortUtil(*itr, visit, s);
		}
		//只有当邻接点都被加入到栈后，这个点才会被加入到栈 
		s.push(v);
	}


public:
	Graph(int V)
	{
		this->V = V;
		adj = new list<int>[V];
	}

	//有向图
	void addEdge(int src, int dest)
	{
		adj[src].push_back(dest);

	}

	void toplogicalSortDFS()
	{
		bool *visit = new bool[V];
		memset(visit, false, sizeof(visit)*V);
		stack<int> s;
		//对每个点遍历，进行拓扑排序。 
		for (int v = 0; v < V; v++)
		{
			if (!visit[v])
				toplogicalSortUtil(v, visit, s);
		}
		while (!s.empty())
		{
			cout << s.top() << " ";
			s.pop();
		}
		cout << endl;

	}


};

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

	cout << "拓扑排序的一种结果是：" << endl;
	g.toplogicalSortDFS();
	system("pause");
	return 0;
}