拓扑排序

拓扑序列：对一个有向无环图($Directed$Directed $Acyclic$Acyclic $Graph$Graph简称$DAG$DAG)$G$G进行拓扑排序，是将$G$G中所有顶点排成一个线性序列，使得图中任意一对顶点$u$u和$v$v，若边$(u,v)∈E(G)$(u,v)∈E(G)，则$u$u在线性序列中出现在$v$v之前。通常，这样的线性序列称为满足拓扑次序($Topological$Topological $Order$Order)的序列，简称拓扑序列

例如，如下有一个图，我们应该采取什么步骤来得到拓扑序列呢？

首先我们可以判断它是$DAG$DAG图，然后我们可以采取如下的步骤：

(1) 选择一个入度为0的顶点输出
(2)然后从图中删除此顶点及所有出边

删除顶点后计算其余顶点的入度，循环(1)(2)步，直到不存在入度为0的顶点为止

这个步骤用上图来描述如下：

于是得到一个拓扑序列：$1 2 4 3 5$12435
通常一个$DAG$DAG图有一个或多个拓扑排序序列

算法实现

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

class Graph {
public:
	Graph(int n);  //构造
	~Graph();  //析构
	void addEdge(int i, int j); //添加有向边
	bool topo_sort(); //拓扑排序
private:
	int n;  //图顶点数
	list<int> *adj;  //邻接表
	stack<int> st;  //存储入度为0的顶点
	int *indegree; //保存入度
};

Graph::Graph(int n) {
	this->n = n;
	adj = new list<int>[n + 1];
	indegree = new int[n + 1];
	//初始化入度为0
	for (int i = 1; i <= n; ++i) {
		indegree[i] = 0;
	}
}

Graph::~Graph() {
	delete []adj;
	delete []indegree;
}

void Graph::addEdge(int i, int j) {
	//添加边i->j，j顶点入度加1
	adj[i].push_back(j);
	++indegree[j];
}

bool Graph::topo_sort() {
	//将顶点入度为0的入栈
	for (int i = 1; i <= n; ++i) {
		if (indegree[i] == 0) 
			st.push(i);
	}
	//计算顶点个数
	int count = 0;
	while (!st.empty()) {
		//取一个入度为0的顶点
		int temp = st.top();
		st.pop(); //出栈
		//输出该顶点
		cout << temp << " ";
		++count;
		//计算删除该顶点之后其余顶点的入度，若为0则入栈
		list<int>::iterator it = adj[temp].begin();
		for (; it != adj[temp].end(); ++it) {
			if (!(--indegree[*it]))
				st.push(*it);
		}
	}
	//如果计算的定点数小于n，则说明有环
	if (count < n)
		return false;
	else
		return true;
}

int main() {
	int n,m;
	int i, j, k;
	ifstream in("input.txt");
	in >> n >> m;
	Graph g(n);
	for (k = 0; k < m; ++k) {
		in >> i >> j;
		g.addEdge(i,j);
	}
	g.topo_sort();
	return 0;
}

$input.txt$input.txt

5 7
1 2
1 4
2 3
2 4
3 5
4 3
4 5

$output$output

1 2 4 3 5

---

一个有向无环图得到的拓扑序列一般不止一种，不同的拓扑序列取决于你每次取入度为0的顶点的顺序，取得顺序不同则拓扑序列也不同。
分析整个算法，对一个具有$n$n个顶点$e$e条弧得$AOV$AOV网来说，将入度为0的顶点入栈的时间复杂度为$O(n)$O(n)，而之后的$while$while循环中，每个顶点进一次栈，出一次栈，入度减1的操作共执行了$e$e次，所以整个算法的时间复杂度为$O(n + e)$O(n+e)