【图论】链式前向星+BFS实现拓扑排序(topSort)
拓扑排序
👏引入
重要概念: 入度:表示一个结点的所有前结点的个数
(图片来源网络,侵删)
问题:给定 n 个结点和 m 个边,然后输入所有的边,输出拓扑排序序列
topsort在网上有很多的介绍,这里就省略,主要讲解拓扑排序的思路。
🤔思路
-
在输入的时候就去记录每一个结点的入度
for (int i = 0; i > u >> v; add(u, v); d[v] ++; //每次插入一条边,后继结点的入度 +1 } // d[v] 表示v结点的入度
-
topsort():
-
先将所有入度为零的结点入队
for (int i = 1; i //遍历所有的结点 if (!d[i]) { //入读为零入队 q[++ tt] = i; } } int t = q[hh ++]; //取出队头元素 for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; //找到出边 d[j] --; //消除影响 if (d[j] == 0) { //如果消除影响后入度为 0,入队 q[++ tt] = j; } } } e[idx] = v, ne[idx] = h[u], h[u] = idx ++; } inline bool topsort() { int hh = 0, tt = -1; for (int i = 1; i //遍历所有的结点 if (!d[i]) { //入读为零入队 q[++ tt] = i; } } while (hh int t = q[hh ++]; //取出队头元素 for (int i = h[t]; i != -1; i = ne[i]) { int j = e[i]; //找到出边 d[j] --; //消除影响 if (d[j] == 0) { //如果消除影响后入度为 0,入队 q[++ tt] = j; } } } return tt == n - 1; //判断是不是无环图,tt == n - 1表示所有的结点都经过了处理 } int main() { cin n m; //n 个结点 m 条边 memset(h, -1, sizeof h); for (int i = 0; i > u >> v; add(u, v); d[v] ++; //每次插入一条边,后继结点的入度 +1 } if (topsort()) { for (int i = 0; i
-
文章版权声明:除非注明,否则均为主机测评原创文章,转载或复制请以超链接形式并注明出处。