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;
}
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.