Graph Overview

Graph-Overview

  1. 最短路
  2. 最小生成树
  3. 二分图
  4. 拓扑排序
  5. 基环树
  6. 欧拉路径

拓扑排序

vector<int> topo_sort(int k, vector<vector<int>> &edges) {
	vector<vector<int>> g(k);
	vector<int> in_deg(k);
	for (auto &e : edges) {
		int x = e[0], y = e[1] ; // 顶点编号从 0 开始,方便计算
		g[x].push_back(y);
		++in_deg[y];
	}
	vector<int> order;
	queue<int> q;
	for (int i = 0; i < k; ++i)
		if (in_deg[i] == 0)
			q.push(i);
		while (!q.empty()) {
			int x = q.front();
			q.pop();
			order.push_back(x);
			for (int y : g[x])	
				if (--in_deg[y] == 0)
					q.push(y);
		}
	return order;
}

BackLink