Topological Sort Algorithm in C++

This C++ program, using an adjacency matrix, displays the times at which the different times at which nodes are visited and left thereby producing a linear ordering of vertices in a graph.
A graph is a set of nodes connected by edges.

Here is the source code of the C++ program to display topological sort. The C++ program is successfully compiled and run on DevCpp, a C++ compiler. The program output is also shown below.

```
/*
```

 * C++ Program for Topological Sorting in Graphs

```
 */
```
```
#include <iostream>
```
```
#include <conio.h>
```
```
using namespace std;
```
```
struct node_info
```
```
{
```
```
    int no;
```
```
    int lv_time, st_time;
```
```
}*q = NULL, *r = NULL;
```
```
struct node
```
```
{
```
```
    node_info *pt;
```
```
    node *next;
```
```
}*top = NULL, *p = NULL, *np = NULL;
```
```
int c = 0;
```
```
void push(node_info *ptr)
```
```
{
```
```
    np = new node;
```
```
    np->pt = ptr;
```
```
    np->next = NULL;
```
```
    if (top == NULL)
```
```
    {
```
```
        top = np;
```
```
    }
```
```
    else
```
```
    {
```
```
        np->next = top;
```
```
        top = np;
```
```
    }
```
```
}
```
```
node_info *pop()
```
```
{
```
```
    if (top == NULL)
```
```
    {
```
```
        cout<<"underflow\n";
```
```
    }
```
```
    else
```
```
    {
```
```
        p = top;
```
```
        top = top->next;
```
```
        return(p->pt);
```
```
        delete(p);
```
```
    }
```
```
}
```
```
void topo(int *v,int am[][7],int i)
```
```
{
```
```
    q = new node_info;
```
```
    q->no = i;
```
```
    q->st_time = c;
```

    cout<<"start time for node no "<<q->no<<":"<<c<<endl;

```
    push(q);
```
```
    v[i] = 1;
```
```
    for (int j = 0; j < 7; j++)
```
```
    {
```

        if (am[i][j] == 0 || (am[i][j] == 1 && v[j] == 1))

```
            continue;
```

        else if(am[i][j] == 1 && v[j] == 0)

```
        {
```
```
            c++;
```
```
            topo(v,am,j);
```
```
        }
```
```
    }
```
```
    c++;
```
```
    r = pop();
```

    cout<<"leave time for "<<r->no<<":"<<c<<endl;

```
    return;
```
```
}
```
```
int main()
```
```
{
```
```
    int v[7],am[7][7];
```
```
    for (int i = 0; i < 7; i++)
```
```
    v[i] = 0;
```
```
    for (int i = 0; i < 7; i++)
```
```
    {
```

        cout<<"enter the values for adjacency matrix row:"<<i + 1<<endl;

```
        for(int j = 0; j < 7; j++)
```
```
        {
```
```
            cin>>am[i][j];
```
```
        }
```
```
    }
```
```
    topo(v,am,0);
```
```
    getch();
```
```
}
```

Output
enter the values for adjacency matrix row:1
0
1
1
0
0
1
1
enter the values for adjacency matrix row:2
1
0
0
0
0
0
0
enter the values for adjacency matrix row:3
1
0
0
0
0
0
1
enter the values for adjacency matrix row:4
0
0
0
0
1
1
0
enter the values for adjacency matrix row:5
0
0
0
1
0
1
1
enter the values for adjacency matrix row:6
1
0
0
1
1
0
0
enter the values for adjacency matrix row:7
1
0
1
0
1
0
0
start time for node no 0:0
start time for node no 1:1
leave time for node no 1:2
start time for node no 2:3
start time for node no 6:4
start time for node no 4:5
start time for node no 3:6
start time for node no 5:7
leave time for node no 5:8
leave time for node no 3:9
leave time for node no 4:10
leave time for node no 6:11
leave time for node no 2:12
leave time for node no 0:13

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Check whether Graph is Biconnected or Not

» Next - C++ Program to Check whether a Graph is Bipartite using 2 Color Algorithm

Related Posts:

Recommended Articles: