请写一段基于深度优先搜索的拓扑排序代码,图的存储使用邻接矩阵
时间: 2023-04-04 21:03:29 浏览: 88
以下是基于深度优先搜索的拓扑排序代码,图的存储使用邻接矩阵:
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 100;
int n; // 图的节点数
int G[MAXN][MAXN]; // 邻接矩阵存储图
void dfs(int u, vector<bool>& vis, stack<int>& st) {
vis[u] = true;
for (int v = 0; v < n; v++) {
if (G[u][v] && !vis[v]) {
dfs(v, vis, st);
}
}
st.push(u);
}
void topological_sort() {
vector<bool> vis(n, false); // 标记是否已经访问过
stack<int> st; // 存储拓扑序列
for (int u = 0; u < n; u++) {
if (!vis[u]) {
dfs(u, vis, st);
}
}
while (!st.empty()) {
cout << st.top() << " ";
st.pop();
}
cout << endl;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> G[i][j];
}
}
topological_sort();
return 0;
}