已知图的邻接表如下所示(“/”表示空指针)，现进行拓扑排序，采用栈存放零入度点，正确拓扑序列是V1V3V5V4V2为什么不是V1V3V5V2V4？ 邻接表如下： 0 V1→2→1→3 / 1 V2 / 2 V3→3→4 / 3 V4 / 4 V5→1→3 /

在进行拓扑排序时，首先需要找到入度为 0 的点，然后将其加入拓扑序列中，并将其指向的点的入度减 1。然后继续寻找入度为 0 的点，直到所有点都被加入拓扑序列中。

根据所给的邻接表，可以计算每个点的入度：

- V1 的入度为 0
- V2 的入度为 1（来自 V1）
- V3 的入度为 1（来自 V1）
- V4 的入度为 2（来自 V1 和 V3）
- V5 的入度为 0

因此，首先将入度为 0 的点加入拓扑序列中，即 V1 和 V5。然后，将 V1 和 V5 指向的点的入度减 1，得到以下邻接表：

0 V1→2→1→3 /
1 V2 /
2 V3→3→4 /
3 V4 /
4 V5→1→3 /

接下来，入度为 0 的点是 V3 和 V2。因为 V3 的入度为 1，所以需要先将其加入拓扑序列中，并将其指向的点的入度减 1。得到以下邻接表：

0 V1→2→1→3 /
1 V2 /
2 V3→4 /
3 V4 /
4 V5→1→3 /

现在入度为 0 的点是 V2 和 V5。因为 V2 的入度为 1，所以需要先将其加入拓扑序列中，并将其指向的点的入度减 1。得到以下邻接表：

0 V1→2→1→3 /
1 /
2 V3→4 /
3 V4 /
4 V5→1→3 /

最后，入度为 0 的点是 V1。将其加入拓扑序列中，并将其指向的点的入度减 1。得到以下邻接表：

0 /
1 /
2 V3→4 /
3 V4 /
4 V5→1→3 /

此时所有点都已经加入拓扑序列中，且没有出现环，因此拓扑排序的结果为 V1V3V5V4V2，而不是 V1V3V5V2V4。

相关问题

9. 已知一个图的顶点集V和边集E分别为： V={1,2,3，4,5，6，7}; E=｛〈2，1>,〈3，2>，〈3，6〉,〈4，3〉,<4,5>,<4,6>,〈5,1>,<5,7〉,〈6,1>,〈6,2〉，〈6,5〉}; 若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。

根据给定的邻接表，我们可以得到各个顶点的入度：

| 顶点 | 入度 |
| --- | --- |
| 1 | 0 |
| 2 | 2 |
| 3 | 1 |
| 4 | 2 |
| 5 | 2 |
| 6 | 3 |
| 7 | 1 |

从入度为0的顶点开始，按照拓扑排序算法，每次选择一个入度为0的顶点并将其从图中删除，直到图为空或不存在入度为0的顶点为止。在这个过程中，选择的顶点序列即为图的拓扑排序。

根据上表，入度为0的顶点有1和4。我们可以从顶点1和4开始，分别将其从图中删除。此时，入度为0的顶点有2和7。我们可以选择其中任意一个顶点，比如选择2，将其从图中删除。然后入度为0的顶点有3和7，选择其中任意一个，比如选择3，将其从图中删除。然后入度为0的顶点有5和7，选择其中任意一个，比如选择5，将其从图中删除。此时入度为0的顶点只剩下7，将其删除后，图为空，得到的拓扑排序为：

1 -> 4 -> 2 -> 3 -> 5 -> 6 -> 7

输入格式: 输入第一行为两个整数n和e，均不超过300。n表示参会人员数。接下来e行，e不超过100，表示已知的两名员工的级别关系，每行为两个整数a和b，表示员工a是员工b的上级。 输出格式: 输出为1行整数，每个整数后一个空格，为n名员工的编号，表示n名员工的发言顺序，如果有多种可能的顺序，则输出字典序最小者。 注：字典序，即对象在字典中的顺序。对于两个数字序列，从第一个数字开始比较，当某一个位置的数字不同时，该位置数字较小的序列，字典序较小，例如1239比1245小。c++

这是一道拓扑排序的经典题目，可以使用BFS或DFS实现。以下是使用BFS实现的示例代码：

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 305;

struct Employee {
    int id, level;
};

vector<int> adj[MAXN];
int inDegree[MAXN];
bool visited[MAXN];
Employee employees[MAXN];

bool cmp(Employee a, Employee b) {
    return a.id < b.id;
}

vector<int> topologicalSort(int n) {
    queue<int> q;
    vector<int> ans;
    for (int i = 1; i <= n; i++) {
        if (inDegree[i] == 0) {
            q.push(i);
        }
    }
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        ans.push_back(u);
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            inDegree[v]--;
            if (inDegree[v] == 0) {
                q.push(v);
            }
        }
    }
    return ans;
}

int main() {
    int n, e;
    cin >> n >> e;
    for (int i = 1; i <= n; i++) {
        employees[i].id = i;
        cin >> employees[i].level;
    }
    sort(employees + 1, employees + n + 1, cmp);
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        adj[b].push_back(a);
        inDegree[a]++;
    }
    vector<int> ans = topologicalSort(n);
    for (int i = 0; i < n; i++) {
        cout << ans[i] << " ";
    }
    return 0;
}

代码思路：

首先定义一个结构体 Employee，表示员工的编号和级别。然后将所有员工按照编号从小到大排序，以便输出时能够按照字典序输出。

接着输入每个员工的级别和已知的上下级关系，用邻接表存储图，同时统计每个节点的入度。

最后使用BFS实现拓扑排序，将排序结果输出即可。