C++-এ গ্রাফে সব ফরওয়ার্ড এজ (Forward Edges) খুঁজে বের করা

এই সেকশনে আমরা একটি গ্রাফে সব ফরওয়ার্ড এজ (forward edges) খুঁজে বের করার C++ প্রোগ্রাম দেখব।

এলগরিদম

topo ফাংশনের জন্য

Begin
    Function topo() ডিক্লেয়ার
    পয়েন্টার v, m[][5] এবং i ইন্টিজার টাইপে ডিক্লেয়ার।
    x = new Node_Inf.
    x->n = i.
    x->S_Time = c.
    Push_Node(x) ফাংশন কল।
    v[i] = 1.
    for (int j = 0; j < 5; j++)
        if (m[i][j] == 0) continue;
        else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j))
            if (x->S_Time < srch_Node(j))
                প্রিন্ট "Forward Edge is between "
                ফরওয়ার্ড এজের মান প্রিন্ট
            continue
        else if (m[i][j] == 1 && v[j] == 0)
            c++;
            প্রিন্ট "Forward Edge is between "
            ফরওয়ার্ড এজের মান প্রিন্ট
            topo(v, m, j) ফাংশন কল
            c++
            x = pop()
            x->L_Time = c
            Store_Node(x) কল করে নোডে ভ্যালু স্টোর
    Return.
End.

উদাহরণ

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

struct Node_Inf {
    int n;
    int L_Time, S_Time;
} *x = NULL, *y = NULL;

struct Node_1 {
    Node_Inf *ptn;
    Node_1 *nxt;
} *tp = NULL, *p = NULL, *npr = NULL;

struct Node_2 {
    Node_2 *lnk;
    Node_Inf *ptn1;
} *hd = NULL, *m = NULL, *n = NULL, *npr1 = NULL;

int c = 0;

void Push_Node(Node_Inf *ptr) {
    npr = new Node_1;
    npr->ptn = ptr;
    npr->nxt = NULL;
    if (tp == NULL) tp = npr;
    else { npr->nxt = tp; tp = npr; }
}

Node_Inf *pop() {
    if (tp == NULL) { cout << "underflow\n"; }
    else { p = tp; tp = tp->nxt; return(p->ptn); delete(p); }
}

void Store_Node(Node_Inf *ptr1) {
    npr1 = new Node_2;
    npr1->ptn1 = ptr1;
    npr1->lnk = NULL;
    if (c == 0) { hd = npr1; m = hd; m->lnk = NULL; c++; }
    else { m = hd; npr1->lnk = m; hd = npr1; }
}

int srch_Node(int j) {
    Node_2 *t = hd;
    while (t != NULL) {
        if ((t->ptn1)->n == j) break;
        else t = t->lnk;
    }
    return (t->ptn1)->L_Time;
}

int Exist_in_Stack(int j) {
    int flag = 0;
    p = tp;
    while (p != NULL) {
        if ((p->ptn)->n == j) { flag = 1; return flag; }
        p = p->nxt;
    }
    return flag;
}

void topo(int *v, int m[][5], int i) {
    x = new Node_Inf;
    x->n = i;
    x->S_Time = c;
    Push_Node(x);
    v[i] = 1;
    for (int j = 0; j < 5; j++) {
        if (m[i][j] == 0) continue;
        else if (m[i][j] == 1 && v[j] == 1 && !Exist_in_Stack(j)) {
            if (x->S_Time < srch_Node(j)) {
                cout << "\nForward Edge is between " << i << " and " << j << endl;
            }
            continue;
        } else if (m[i][j] == 1 && v[j] == 0) {
            c++;
            cout << "\nForward Edge is between " << i << " and " << j << endl;
            topo(v, m, j);
        }
    }
    c++;
    x = pop();
    x->L_Time = c;
    Store_Node(x);
    return;
}

int main() {
    int v[5], m[5][5];
    for (int i = 0; i < 5; i++) v[i] = 0;
    for (int i = 0; i < 5; i++) {
        cout << " Enter the values of matrix::" << i+1 << endl;
        for(int j = 0; j < 5; j++) cin >> m[i][j];
    }
    topo(v, m, 0);
    getch();
}

আউটপুট

Enter the values of matrix:1
0 1 0 1 0
Enter the values of matrix:2
1 0 0 1 0
Enter the values of matrix:3
1 0 0 0 1
Enter the values of matrix:4
0 1 1 0 0
Enter the values of matrix:5
1 1 0 0 0
Forward Edge is between 0 and 1
Forward Edge is between 1 and 3
Forward Edge is between 3 and 2
Forward Edge is between 2 and 4
Forward Edge is between 0 and 3