c++graphgraph-theorydepth-first-searchtopological-sort

Topological sort not printing all vertexes


I am coding the geeksforgeeks topological sort implementation using an adjacency matrix instead of an edge list. I have structured the code similarly to the c++ example but cannot get mine to visit and print all nodes. I know that I have to begin at a vertex with indegree 0 but neither vertex 4 or 5(which have indegree 0) work for my code. The example implementation and illustrated graph that I am using can be found here https://www.geeksforgeeks.org/topological-sorting/ The expected output when starting from vertex 5 is 542310 but my code is outputting 52310. The expected output when starting from 4 is 452310 but my code outputs 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;
}


Solution

  • Your code is missing this part

    // 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); 
    

    from the linked code. When you start only from e.g. 4, you can verify in the linked drawing that only 0 and 1 are reachable in the example graph.