用DEV C++写一个程序对有向无环图,按照有向图给出的次序关系,将图中顶点排成一个线性序列,对于有向图中没有限定次序关系的顶点,则可以人为加上任意的次序关系。由此所得顶点的线性序列称之为拓扑有序序列。 输入有向图的相关信息,若图中无环,输出其拓扑有序序列,否则输出“此有向图不是有向无环图”。 因拓扑有序序列不唯一,故要求如下: (1)使用邻接表存储图。邻接表的每个链表中,要求按顶点的序号从大到小排列; (2)使用栈辅助操作。初始时,入度为0的顶点入栈时,也按顶点的序号从大到小的顺序入栈。 输入说明: 输入有向图的顶点数、边数、各顶点的值,各边的信息。 输出说明: 若有向图中无环,输出其拓扑有序序列,否则输出“此有向图不是有向无环图”。 拓扑有序序列的每个顶点数据后有一个空格。
时间: 2024-02-20 11:58:53 浏览: 82
有向图若有环,输出环,否则,拓扑排序
3星 · 编辑精心推荐
以下是用C++语言编写的程序,可实现对有向无环图进行拓扑排序:
```cpp
#include <iostream>
#include <stack>
#include <vector>
#include <algorithm>
using namespace std;
const int MAXN = 10005;
struct Edge {
int to, next;
};
Edge edges[MAXN];
int head[MAXN], inDegree[MAXN];
int N, M, cnt;
void addEdge(int from, int to) {
edges[++cnt].to = to;
edges[cnt].next = head[from];
head[from] = cnt;
inDegree[to]++;
}
bool topSort() {
stack<int> st;
for (int i = 1; i <= N; i++) {
if (inDegree[i] == 0) st.push(i);
}
vector<int> ans;
while (!st.empty()) {
int u = st.top();
st.pop();
ans.push_back(u);
for (int i = head[u]; i; i = edges[i].next) {
int v = edges[i].to;
inDegree[v]--;
if (inDegree[v] == 0) st.push(v);
}
}
if (ans.size() != N) return false;
reverse(ans.begin(), ans.end());
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return true;
}
int main() {
cin >> N >> M;
for (int i = 1; i <= M; i++) {
int from, to;
cin >> from >> to;
addEdge(from, to);
}
if (!topSort()) cout << "此有向图不是有向无环图";
return 0;
}
```
使用邻接表存储图,并使用一个 stack 存储入度为 0 的节点,在每次取出一个节点后更新其相邻节点的入度,并将入度为 0 的节点压入栈中。最终,如果所有节点都被排列,则说明拓扑排序成功,输出拓扑有序序列;否则,输出“此有向图不是有向无环图”。
阅读全文