拓扑排序不打印所有顶点

Question

我正在使用邻接矩阵而不是边列表对 geeksforgeeks 拓扑排序实现进行编码。我的代码结构类似于 c++ 示例，但无法让我访问和打印所有节点。我知道我必须从入度为 0 的顶点开始，但顶点 4 或 5（入度为 0）都不适合我的代码。我正在使用的示例实现和插图图可以在这里找到 https://www.geeksforgeeks.org/topological-sorting/ 从顶点 5 开始时的预期输出是 542310 但我的代码输出 52310。从 4 开始时的预期输出是 452310 但我的代码输出 410 .

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> topoSort(int A[6][6], int start);
void topoSortHelper(int A[6][6], int start, vector<bool>& visited, stack<int>& s);

vector<int> topoSort(int A[6][6], int start)
{
    vector<bool> visited(6,false);
    stack<int> s;
    vector<int> result;

    for(int i = 0; i < 6; i++)
    {
        visited[i] = false;
    }
    visited[start] = true;

    topoSortHelper(A, start, visited, s);

    while(!s.empty())
    {
        cout << s.top();
        s.pop();
    }

    return result;
}
void topoSortHelper(int A[6][6], int start, vector<bool>& visited, stack<int>& s)
{
    for(int i = 0; i < 6; i++)
    {
        if(A[start][i] == 1 && visited[i] == false)
        {
            visited[i] = true;
            topoSortHelper(A, i, visited, s);
        }
    }
    s.push(start);
}
int main()
{
    int A[6][6] = 
    {
        {0, 0, 0, 0, 0, 0}, 
        {0, 0, 0, 0, 0, 0}, 
        {0, 0, 0, 1, 0, 0}, 
        {0, 1, 0, 0, 0, 0}, 
        {1, 1, 0, 0, 0, 0}, 
        {1, 0, 1, 0, 0, 0} 
    };
    vector<int> result = topoSort(A, 5);

    for(auto i: result)
    {
        cout << i;
    }
    return 0;
}

Answer 1

您的代码缺少这部分

// Call the recursive helper function to store Topological 
// Sort starting from all vertices one by one 
for (int i = 0; i < V; i++) 
  if (visited[i] == false) 
    topologicalSortUtil(i, visited, Stack);

来自链接代码。当您仅从例如开始时4，您可以在链接的绘图中验证示例图中只有 0 和 1 是可达的。

拓扑排序不打印所有顶点

Topological sort not printing all vertexes

c++

graph

graph-theory

depth-first-search

topological-sort