算法可视化
数据结构
拓扑排序:课程安排
有向无环图,有些任务要先做(Kahn 算法):每次拿走入度为 0 的节点(没有前置依赖的)。
main.cpp第 2 行
1// 拓扑排序: 每次取出入度为 0 的节点(Kahn)
2for (每个节点) indeg[v] = 入边数量;
3queue<int> q; 入度为 0 的节点入队;
4while (!q.empty()) {
5 int u = q.front(); q.pop();
6 cout << u; // 输出拓扑序
7 for (v : adj[u])
8 if (--indeg[v] == 0) q.push(v);
9}
变量表0 个变量
还没有变量,执行到声明语句后出现
图(节点 + 边)
1/20
计算每个节点的入度(指向它的边数):0:0, 1:1, 2:1, 3:2, 4:1, 5:1
1 / 20