C++ :: Topological Sort Algorithm (using INDEGREE)

A topological sort of a dag G = (V,E) is a linear ordering of all its vertices such that if G contains an edge (u,v), then u appears before v in the ordering. (If the graph contains a cycle, then no linear ordering is possible.)

ALGORITHM

TOPOLOGICAL-SORT(S)
    Find the indegree INDEG(N) of each node N of S. (This can be done by traversing each adjacency matrix.)
    Put in a queue all the nodes with zero indegree.
    Repeat Steps 5 and 6 until the queue is empty.
        Remove the front node N of the queue.
        Repeat the following for each neighbor M of the node N:
            (a) Set INDEG(M) := INDEG(M) - 1.
                [This deletes the edge from N to M.]
            (b) If INDEG(M) = 0, then: Add M to the rear of the queue.
        [End of loop.]
    [End of Step 3 loop.]
    Exit.    

C++ Code

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define MAX 101
using namespace std;

int INDEG[MAX], node, edge;

vector<int> TOPOLOGICAL_SORT(int [][MAX]);

int main(void)
{
    //freopen("toposort.txt", "r", stdin);
    int adjMatrix[MAX][MAX];
    for(int i=0; i<MAX; i++)
        for(int j=0; j<MAX; j++) {
            adjMatrix[i][j] = 0;
            INDEG[i] = 0;
        }
    int M, N;
    cin >> node >> edge;
    for(int e=1; e<=edge; e++) {
        cin >> M >> N;
        adjMatrix[M][N] = 1;
        INDEG[N]++;
    }
    vector<int> orderedList = TOPOLOGICAL_SORT(adjMatrix);
    for(int i=0; i<orderedList.size(); i++) {
        cout << orderedList[i] << ends;
    }
    return 0;
}

vector<int> TOPOLOGICAL_SORT(int S[][MAX]) {

    queue<int> Q;

    for(int n=1; n<=node; n++) {
        if(INDEG[n] == 0) Q.push(n);
    }

    vector<int> topoList;

    while( !Q.empty()) {
        int N = Q.front(); Q.pop();
        topoList.push_back(N);
        for(int M=1; M<=node; M++) {
            if(S[N][M] == 1) {
                INDEG[M]--;
                if(INDEG[M] == 0) {
                    Q.push(M);
                }
            }
        }
    }
    return topoList;
}

Sample Input

5 4
1 2
2 3
1 3
1 5

Sample Output

1 4 2 5 3

Topological Sort Related UVa Problems

• 124 - Following orders
• 196 - Spreadsheet
• 200 - Rare Order
• 872 – Ordering
• 10305 - Ordering Tasks
• 11060 – Beverages

Refference: Data Structures - Seymour Lipschutz