DAG vs Topological Sort - tenji/ks GitHub Wiki
在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（英语：Directed Acyclic Graph，缩写：DAG）。
有向无环图和树是什么关系？
因为有向无环图中从一个点到另一个点有可能存在两种路线，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。
更多关于图的内容，传送门
Kahn 是广度优先搜索（BFS）吗？
Kahn's algorithm is almost a BFS.
- 识别没有入度的顶点；
- 将该顶点添加到队列；
- 将该顶点从图中删除，对应的就是出队列以及依赖该顶点的顶点入度减一；
- 重复以上流程。
以上循环会在不再有入度为零的顶点时结束。发生这种情况的原因有两个：
- 没有剩余顶点。我们已将它们全部从图中取出，并将它们添加到拓扑排序中；
- 还剩下一些顶点，但它们都有传入边（Incoming Edge）。这意味着该图有环，并且不存在拓扑排序。
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is not empty do
// 入度为零的顶点出队
remove a node n from S
insert n into L
for each node m with an edge e from n to m do
// 将该顶点从图中删除，对应的就是出队列以及依赖该顶点的顶点入度减一
remove edge e from the graph
// 没有入度的顶点加入队列
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (a topologically sorted order)
假设 E 表示边的数量；V 表示节点的数量。
- 时间复杂度：
O(E + V) - 空间复杂度：
O(V)
使用邻接表存储图，关于邻接表，传送门
import java.util.*;
public class Main {
// Function to return array containing vertices in
// Topological order.
public static int[] topologicalSort(List<List<Integer> > adj, int V)
{
// Array to store indegree of each vertex
int[] indegree = new int[V];
for (int i = 0; i < V; i++) {
for (int it : adj.get(i)) {
indegree[it]++;
}
}
// Queue to store vertices with indegree 0
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < V; i++) {
if (indegree[i] == 0) {
q.offer(i);
}
}
int[] result = new int[V];
int index = 0;
while (!q.isEmpty()) {
int node = q.poll();
result[index++] = node;
// Decrease indegree of adjacent vertices as the
// current node is in topological order
for (int it : adj.get(node)) {
indegree[it]--;
// If indegree becomes 0, push it to the
// queue
if (indegree[it] == 0) {
q.offer(it);
}
}
}
// Check for cycle
if (index != V) {
System.out.println("Graph contains cycle!");
return new int[0];
}
return result;
}
public static void main(String[] args)
{
// Number of nodes
int n = 6;
// Edges
int[][] edges = { { 0, 1 }, { 1, 2 }, { 2, 3 },
{ 4, 5 }, { 5, 1 }, { 5, 2 } };
// Graph represented as an adjacency list
List<List<Integer> > adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
adj.add(new ArrayList<>());
}
// Constructing adjacency list
for (int[] edge : edges) {
adj.get(edge[0]).add(edge[1]);
}
// Performing topological sort
System.out.println("Topological sorting of the graph: ");
int[] result = topologicalSort(adj, n);
// Displaying result
for (int i : result) {
System.out.print(i + " ");
}
}
}- 创建一个具有
n个顶点和m向边的图； - 初始化一个堆栈和一个大小为
n的数组记录已访问的顶点； - 对于图中每个未访问的顶点，执行以下操作：
- 以顶点为参数调用 DFS 函数；
- 在 DFS 函数中，将顶点标记为已访问，并对顶点的所有未访问邻居递归调用 DFS 函数；
- 一旦访问了所有邻居，就将顶点压入堆栈。
- 操作完成之后，顶点已被访问过，从堆栈中弹出元素并将它们追加到输出列表中，直到堆栈为空；
- 结果列表是图的拓扑排序顺序。
L ← Empty list that will contain the sorted nodes
while exists nodes without a permanent mark do
select an unmarked node n
visit(n)
function visit(node n)
if n has a permanent mark then
return
if n has a temporary mark then
stop (graph has at least one cycle)
mark n with a temporary mark
for each node m with an edge from n to m do
visit(m)
mark n with a permanent mark
add n to head of L
假设 E 表示边的数量；V 表示节点的数量。
- 时间复杂度：
O(E + V) - 空间复杂度：
O(V)
import java.util.*;
public class TopologicalSort {
// Function to perform DFS and topological sorting
static void topologicalSortUtil(int v, List<List<Integer> > adj,
boolean[] visited,
Stack<Integer> stack)
{
// Mark the current node as visited
visited[v] = true;
// Recur for all adjacent vertices
for (int i : adj.get(v)) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);
}
// Push current vertex to stack which stores the
// result
stack.push(v);
}
// Function to perform Topological Sort
static void topologicalSort(List<List<Integer> > adj, int V)
{
// Stack to store the result
Stack<Integer> stack = new Stack<>();
boolean[] visited = new boolean[V];
// Call the recursive helper function to store
// Topological Sort starting from all vertices one
// by one
for (int i = 0; i < V; i++) {
if (!visited[i])
topologicalSortUtil(i, adj, visited, stack);
}
// Print contents of stack
System.out.print("Topological sorting of the graph: ");
while (!stack.empty()) {
System.out.print(stack.pop() + " ");
}
}
// Driver code
public static void main(String[] args)
{
// Number of nodes
int V = 4;
// Edges
List<List<Integer> > edges = new ArrayList<>();
edges.add(Arrays.asList(0, 1));
edges.add(Arrays.asList(1, 2));
edges.add(Arrays.asList(3, 1));
edges.add(Arrays.asList(3, 2));
// Graph represented as an adjacency list
List<List<Integer> > adj = new ArrayList<>(V);
for (int i = 0; i < V; i++) {
adj.add(new ArrayList<>());
}
for (List<Integer> i : edges) {
adj.get(i.get(0)).add(i.get(1));
}
topologicalSort(adj, V);
}
}一般情况下，拓扑排序并非唯一。有向无环图仅仅在存在一条路径可以包含其所有顶点的情况下，有唯一的拓扑排序方式，这时，拓扑排序与它们在这条路径中出现的顺序相同。
- Directed acyclic graph 维基百科
- 拓扑排序 OI Wiki
- Kahn’s algorithm for Topological Sorting Kahn 算法实现
- Topological Sorting 深度优先搜索实现
- Topological Sort