C++-এ টপোলজিক্যাল সোর্ট (Topological Sort) ব্যবহার করে গ্রাফে সাইকেল (Cycle) চেক করা

একটি ডায়রেক্টেড্যাসাইক্লিক গ্রাফ (DAG) এর ভার্টেক্সগুলো টপোলজিক্যাল সোর্ট ব্যবহার করে লিনিয়ার অর্ডারে সর্ট করা যায়।

টপোলজিক্যাল সোর্ট শুধু DAG-এ কাজ করে। একটি DAG-এ একাধিক টপোলজিক্যাল সোর্ট থাকতে পারে।

আমরা একটি C++ প্রোগ্রাম দেখব, যা টপোলজিক্যাল সোর্ট করবে গ্রাফে সাইকেল (cycle) আছে কিনা চেক করতে।

উদাহরণ

এলগরিদম

Topological Sort:
Begin
    topo_sort(int *v, int T_S[][5], int i) ফাংশন ডিক্লেয়ার
    a = new NodeInfo.
    a->n = i
    a->S_Time = cn.
    push_node(a) কল করে ডেটা ইনসার্ট।
    v[i] = 1.
    for (int j = 0; j < 5; j++)
        if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) continue.
        else if(T_S[i][j] == 1 && v[j] == 0)
            cn++.
            topo_sort(v, T_S, j) কল।
    cn++.
    a = pop().
    a->L_Time = cn.
    Store_Node(a).
End.

উদাহরণ

#include <iostream>
#include <conio.h>
using namespace std;

struct NodeInfo { int n; int L_Time, S_Time; } *a = NULL;
struct Node { NodeInfo *ptr; Node *nxt; } *t = NULL, *b = NULL, *npt = NULL;
struct Node_Link { Node_Link *lk; NodeInfo *ptr1; } *hd = NULL, *m = NULL, *n = NULL, *npt1 = NULL;
int cn = 0;
bool flag = false;

void push_node(NodeInfo *pt) { /* ... */ }
NodeInfo *pop() { /* ... */ }
void Store_Node(NodeInfo *pt1) { /* ... */ }
void delete_node(int x) { /* ... */ }

void topo_sort(int *v, int T_S[][5], int i) {
    a = new NodeInfo;
    a->n = i;
    a->S_Time = cn;
    push_node(a);
    v[i] = 1;
    for (int j = 0; j < 5; j++) {
        if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) continue;
        else if(T_S[i][j] == 1 && v[j] == 0) {
            cn++;
            topo_sort(v, T_S, j);
        }
    }
    cn++;
    a = pop();
    a->L_Time = cn;
    Store_Node(a);
    return;
}

void topologic_sort(int *v, int T_S[][5], int i) {
    v[i] = 1;
    delete_node(i);
    for (int j = 0; j < 5; j++) {
        if (T_S[i][j] == 0 || (T_S[i][j] == 1 && v[j] == 1)) continue;
        else if(T_S[i][j] == 1 && v[j] == 0)
            topologic_sort(v, T_S, j);
    }
    return;
}

void Insert_Edge(int T_S[][5], int source, int destination) {
    T_S[source][destination] = 1;
    return;
}

int main() {
    int v[5], T_S[5][5], T_S_N[5][5], cn = 0, a, b;
    for (int i = 0; i < 5; i++) v[i] = 0;
    for (int i = 0; i < 5; i++)
        for (int j = 0; j < 5; j++)
            T_S[i][j] = 0;
    while (cn < 5) {
        cout << "Enter the source: "; cin >> a;
        cout << "Enter the destination: "; cin >> b;
        cout << endl;
        Insert_Edge(T_S, a, b);
        cn++;
    }
    topo_sort(v, T_S, 0);
    for (int i = 0; i < 5; i++) {
        v[i] = 0;
        for (int j = 0; j < 5; j++)
            T_S_N[j][i] = T_S[i][j]; // ট্রান্সপোজ (transpose)
    }
    if (hd != NULL) {
        topologic_sort(v, T_S_N, (hd->ptr1)->n);
        if (flag == false)
            cout << "There is a cycle in this graph...\n";
    }
    getch();
}

আউটপুট

Enter the source: 0
Enter the destination: 1
Enter the source: 1
Enter the destination: 2
Enter the source: 2
Enter the destination: 3
Enter the source: 3
Enter the destination: 4
Enter the source: 4
Enter the destination: 0
There is a cycle in this graph...