CODEWITHSUNDEEP
algorithmgraphtreegraph-algorithm
tryst001
tryst001

Reputation: 11

How to find edges in route

Let's say I have a graph like this sample graph

I want to find all the edges from 1 to 3 i.e. 1 2... 2 4... 4 3. I can write the code for 1 to 5 quite easily but when the next node in descending order then my code doesn't work. Please help me with that.

Here is my code:- given if there is edge between i and j then:- arr[i][j]=0 where s is total number of nodes and i have to find edges between a and b 

for(int i=a;i!=b;)
   {
        for(int j=1;j<=s;j++)
        {
             if(arr[i][j]==0)
             {
           //cout<<i<<" "<<j<<endl;
           i=j;
             }
        }
   }

Upvotes: 0

Views: 55

Answers (1)

uSeemSurprised
uSeemSurprised

Reputation: 1834

This can be solved using Breadth first search algorithm we can keep track of the parent of the current node while performing a BFS, and then can construct the path from that if the path exists, i have written a c++ solution below

#include<iostream>
#include<queue>

using namespace std;

int n, arr[100][100], par[100], vis[100], ans[100];

void bfs(int start, int end){
    queue<int> Q;
    Q.push(start);
    par[start] = -1;vis[start] = 1;
    bool found = false;
    while(Q.size() > 0){
        int v = Q.front();
        Q.pop();
        if(v == end){
            found = true;
            break;
        }
        for(int i = 1;i <= n;i++){
            if(arr[v][i] == 0 || vis[i] == 1) continue;
            Q.push(i);vis[i] = 1;
            par[i] = v;
        }
    }
    if(found == false){
        cout << "No Path Found" << endl;return;
    }
    int curr = end, len = 0;
    while(curr != -1){
        ans[len++] = curr;
        curr = par[curr];
    }
    for(int i = len-1;i >= 1;i--) cout << ans[i] << " " << ans[i-1] << endl;
}

int main(){
    n = 5;
    arr[1][2] = 1;arr[2][1] = 1;
    arr[2][4] = 1;arr[4][2] = 1;
    arr[4][5] = 1;arr[5][4] = 1;
    arr[3][4] = 1;arr[4][3] = 1;

    bfs(1, 3);

    return 0;
}

Link to solution on Ideone : http://ideone.com/X8QnNu

Upvotes: 0

Related Questions