拓扑排序代码

拓扑排序是一种常用于解决依赖关系问题的算法，通常用于有向无环图（DAG）的排序。拓扑排序的本质是找到一种合理的顺序方式，以便在该顺序下，每个节点的依赖都已被满足，可以被正确处理。

下面，我们从多个角度分析拓扑排序代码。

1. 算法原理

拓扑排序的算法原理是，每次先找到图中没有依赖的节点，将其加入到排序序列中，然后将该节点从图中删除，继续寻找没有依赖的节点，以此类推，直到所有节点都被加入到排序序列中。

2. 实现方法

拓扑排序可以使用多种方法实现，以下是其中比较常用的两种方法。

（1）队列实现

首先，需要遍历整个图，统计每个节点的入度。然后，将所有入度为0的节点加入到队列中。当队列不为空时，从队列中取出一个元素，将其加入到排序序列中，并将该节点的所有出边的节点的入度减1，如果减1后该节点的入度为0，则将其加入到队列中。

（2）递归实现

首先，需要选择一个入度为0的节点，将其加入到排序序列中。然后，递归调用拓扑排序函数，将以该节点为起点的所有出边的节点依次加入到排序序列中。

3. 时间复杂度

拓扑排序的时间复杂度为O(n+m)，其中n是节点数，m是边数。具体的实现方法会对时间复杂度产生影响。

4. 拓扑排序代码

以下是使用队列实现拓扑排序的代码：

```c++

void topo_sort(queue & q, vector & indegree, vector >& graph, vector & res) {

while (!q.empty()) {

int cur = q.front();

q.pop();

res.push_back(cur);

for (int i = 0; i < graph[cur].size(); i++) {

int next = graph[cur][i];

indegree[next]--;

if (indegree[next] == 0) {

q.push(next);

}

}

}

}

vector topo_sort(vector >& edges, int n) {

vector > graph(n + 1);

vector indegree(n + 1, 0);

vector res;

for (int i = 0; i < edges.size(); i++) {

int u = edges[i][0], v = edges[i][1];

graph[u].push_back(v);

indegree[v]++;

}

queue q;

for (int i = 1; i <= n; i++) {

if (indegree[i] == 0) {

q.push(i);

}

}

topo_sort(q, indegree, graph, res);

return res;

}

```

以下是使用递归实现拓扑排序的代码：

```c++

void dfs(int cur, vector & visited, vector >& graph, vector & res) {

visited[cur] = 1;

for (int i = 0; i < graph[cur].size(); i++) {

int next = graph[cur][i];

if (!visited[next]) {

dfs(next, visited, graph, res);

}

}

res.push_back(cur);

}

vector topo_sort(vector >& edges, int n) {

vector > graph(n + 1);

vector visited(n + 1, 0);

vector res;

for (int i = 0; i < edges.size(); i++) {

int u = edges[i][0], v = edges[i][1];

graph[u].push_back(v);

}

for (int i = 1; i <= n; i++) {

if (!visited[i]) {

dfs(i, visited, graph, res);

}

}

reverse(res.begin(), res.end());

return res;

}

```

5. 全文摘要和

【关键词】本文从算法原理、实现方法、时间复杂度等多个角度分析了拓扑排序代码，给出了使用队列实现和递归实现的代码实现，并且说明了实现方法对时间复杂度的影响。本文的关键词包括拓扑排序、有向无环图、入度、时间复杂度、队列实现、递归实现。