Topological Sort

on
#include <iostream>
#define M 20

using namespace std;

int adj[M][M], c[M], p[M], d[M], f[M], time;

typedef struct stack
{
    int arr[M];
    int top;
} stack;

void init(stack *s)
{
    s->top = -1;
}

bool isempty(stack *s)
{
    return s->top == -1;
}

bool isfull(stack *s)
{
    return s->top == M - 1;
}

int pop(stack *s)
{
    if (isempty(s))
    {
        return 99999;
    }
    else
    {
        int temp = s->arr[s->top];
        --s->top;
        return temp;
    }
}

void push(stack *s, int data)
{
    if (isfull(s))
    {
        return;
    }
    else
    {
        ++s->top;
        s->arr[s->top] = data;
    }
}

void dfs_visit(int i, int v, stack *s)
{
    int j;
    c[i] = 1;
    ++time;
    d[i] = time;

    for (j = 0; j < v; j++)
    {
        if (adj[i][j] == 1 && c[j] == 0)
        {
            p[j] = i;
            dfs_visit(j, v, s);
        }
    }
    c[i] = 2;
    ++time;
    f[i] = time;
    push(s, i);
}

void dfs(int v, stack *s)
{
    int i;

    time = 0;
    for (i = 0; i < v; i++)
    {
        c[i] = 0;
        p[i] = -1;
    }
    for (i = 0; i < v; i++)
    {
        if (c[i] == 0)
        {
            dfs_visit(i, v, s);
        }
    }
}

void topologicalSort(int v)
{
    stack s;
    init(&s);
    dfs(v, &s);

    cout << "Topological Sorting: ";
    while (!isempty(&s))
    {
        cout << pop(&s) << " ";
    }
    cout << endl;
}

int main()
{
    int v, i, j;
    cout << "Enter the number of vertices: ";
    cin >> v;

    cout << "Enter the adjacency matrix:" << endl;
    for (i = 0; i < v; i++)
    {
        for (j = 0; j < v; j++)
        {
            cin >> adj[i][j];
        }
    }

    // Perform topological sorting
    topologicalSort(v);

    return 0;
}

Comments

Post a Comment