C++ प्रोग्राम: ग्राफ में सभी फॉरवर्ड एजेस खोजें

इस सेक्शन में, हम एक C++ प्रोग्राम पर विचार करेंगे जो ग्राफ में सभी फॉरवर्ड एजेस खोजता है।

एल्गोरिदम

टोपो फंक्शन के लिए

Begin
    फंक्शन 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;
            continue;
        }
    }
    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);
    return 0;
}

आउटपुट

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

DFS ट्रैवर्सल में फॉरवर्ड एज एक नॉन-ट्री एज है जो डीएफएस ट्री में किसी नोड को उसके वंशज से जोड़ता है। यह प्रोग्राम DFS के दौरान डिस्कवरी/फिनिश टाइम्स (S_Time, L_Time) का उपयोग करके फॉरवर्ड एजेस का पता लगाता है। एक एज (u,v) फॉरवर्ड एज है यदि v पहले से विजिटेड है (v[j]==1), स्टैक में नहीं है, और u का डिस्कवरी टाइम v के डिस्कवरी टाइम से कम है।