C++输出有向无环图的所有拓扑序列

    科技2022-07-20  103

    输出有向无环图的所有拓扑序列

    1,基本思想2,代码实现

    1,基本思想

    输出有向无环图的其中一个拓扑序列比较简单,输出所有的拓扑序列则要用到回溯的思想和递归的方法。这里暂不对回溯法做解释。

    2,代码实现

    #include<iostream> #include<vector> using namespace std; #define Max 9999 vector<int> result; //用来保存并输出拓扑结果 int n, m; //n 为顶点数, m 为边数 int G[Max][Max]; bool visited[Max]; int inDegree[Max]; //记录各个顶点的入度 void dfs() { if (result.size() == n) { for (int i = 0; i < n; ++i) { cout << result[i] << " "; } cout << endl; return; } for (int i = 0; i < n; ++i) { if (!visited[i] && inDegree[i] == 0) { result.push_back(i); visited[i] = true; for (int j = 0; j < n; ++j) { if (G[i][j] > 0) { inDegree[j]--; } } dfs(); result.pop_back(); visited[i] = false; for (int j = 0; j < n; ++j) { if (G[i][j] > 0) { inDegree[j]++; } } } } return; } int main() { cout << "输入顶点数:"; cin >> n; cout << "输入边数:"; cin >> m; fill(G[0], G[0] + Max * Max, 0); fill(visited, visited + Max, false); fill(inDegree, inDegree + Max, 0); cout << "输入各条边的信息:"; int u, v; //u为边的出发点, v为边的终点 for (int i = 0; i < m; ++i) { cin >> u >> v; G[u][v]++; inDegree[v]++; } dfs(); return 0; }

    输入输出信息:

    Processed: 0.012, SQL: 8