拓扑排序学习笔记

<h1><a id="_0"></a>拓扑排序</h1> 拓扑排序是对一张 有向 并且 无环 的图进行遍历排序。 如果在图中所有的节点构成的序列AAA中，对于每一条边(x,y)(x, y)(x,y)：xxx都出现在yyy的前面，则序列AAA就为这张图的拓扑序。 <h4><a id="_4"></a>关于入度和出度</h4> 入度：以节点xxx为终点的有向边的条数被称为xxx的入度。记作 deg(x)deg(x)deg(x) . 出度：以节点xxx为起点的有向边的条数被称为xxx的出度。 <img src="https://uploadfiles.nowcoder.com/images/20201011/271749033_1602394156105_5A9F6A51E994577B680762E995D412F0"> 例如在此图中，节点3的入度就为2 ，节点4的入度也为2. <h3><a id="_10"></a>思想</h3> 不断选择图中入度为0的节点入队（如上图中的节点5、2、 1）。 再将xxx连向的节点的入度减一。 <h3><a id="_14"></a>实现</h3> 1.建一个空的拓扑序列AAA。 2.预处理入度，将入度是0的节点全部入队。 3.取出队头，此时的对头xxx一定是入度为0的节点，所以A[++cnt]=x;A[++ cnt] = x;A[++cnt]=x; 4.对于此时的队头xxx，把所连的yyy的入度减一，即deg[y]−−;deg[y] --;deg[y]−−; 5.操作至队列为空，此时A[]A[]A[]则为这张图的拓扑排序。 6.在最后将A[]A[]A[]的长度检查以下，即看此时的cntcntcnt是否为图中的节点个数，如果少于了节点数，则说明图中有环。 <h4><a id="_22"></a>图示</h4> 初始图 <img src="https://uploadfiles.nowcoder.com/images/20201011/271749033_1602394156195_5A9F6A51E994577B680762E995D412F0"> 1.建立空序列 2.2.预处理入度，将入度是0的节点全部入队。 <img src="https://uploadfiles.nowcoder.com/images/20201011/271749033_1602394156514_5A9F6A51E994577B680762E995D412F0"> 3.取出队头，此时的对头xxx一定是入度为0的节点，所以A[++cnt]=x;A[++ cnt] = x;A[++cnt]=x; 4.对于此时的队头xxx，把所连的yyy的入度减一，即deg[y]−−;deg[y] --;deg[y]−−; 5.操作至队列为空，此时A[]A[]A[]则为这张图的拓扑排序。 <img src="https://uploadfiles.nowcoder.com/images/20201011/271749033_1602394156862_5A9F6A51E994577B680762E995D412F0"> 6.在最后将A[]A[]A[]的长度检查以下，即看此时的cntcntcnt是否为图中的节点个数，此时发现少了三个节点，所以图中含有环，即(2,4)(4,6)(6,2)(2, 4) (4, 6)(6, 2)(2,4)(4,6)(6,2)。 <h3><a id="_35"></a>代码</h3> 本人太菜了，邻接表出了点玄学错误，就只能用矩阵。。。 <pre><code class="prism language-cpp">#include <queue> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int MAXN = 10005; int n, m, cnt; bool a[MAXN][MAXN]; int deg[MAXN], ans[MAXN]; queue<int> q; void topsort(void) { for (int i = 1; i <= n; i++) if (deg[i] == 0) q.push(i); while (!q.empty()) { const int u = q.front(); ans[++cnt] = u; q.pop(); for (int i = 1; i <= n; i++) if (a[u][i]) { deg[i]--; if (deg[i] == 0) q.push(i); } } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int x, y; scanf("%d %d", &x, &y); a[x][y] = 1; deg[y]++; } topsort(); if (cnt < n) { printf("no solution\n"); } else { for (int i = 1; i <= cnt; i++) { printf("%d ", ans[i]); } } return 0; } //邻接表的锅突然修好 </code></pre> <pre><code>#include <vector> #include <queue> #include <cstdio> #include <iostream> #include <algorithm> using namespace std; const int MAXN = 20005; int n, m, deg[MAXN], ans[MAXN], cnt; bool a[MAXN][MAXN]; queue<int> q; vector<int> G[MAXN]; void topsort() { for (int i = 1; i <= n; i++) { if (deg[i] == 0) q.push(i); } while (q.size()) { int u = q.front(); ans[++cnt] = u; q.pop(); for (int i = 0; i < G[u].size(); i++) { deg[G[u][i]]--; if (deg[G[u][i]] == 0) { q.push(G[u][i]); } } } } int main() { scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++) { int x, y; scanf("%d %d", &x, &y); G[x].push_back(y); deg[y]++; } topsort(); if (cnt < n) { printf("no solution\n"); } else { for (int i = 1; i <= cnt; i++) { printf("%d ", ans[i]); } } return 0; }</code></pre> <pre><code class="prism language-cpp"> </code></pre>