×

DS - Basics

DS - Array

DS - Linked List

DS - Stack

DS - Queue

DS Hashing

DS Tree

DS - Graph

DS Programs Using C/C++

DS - Miscellaneous Topics

Count all the possible path between two vertices

In this article, we are going to see how to find number of all possible paths between two vertices? Submitted by Souvik Saha, on March 26, 2019

What to Learn?

How to count all possible paths between two vertices?

In the graph there are many alternative paths from vertex 0 to vertex 4

    1.	0 → 1 → 2 → 3 → 4
    2.	0 → 1 → 4
    3.	0 → 3 → 2 → 1 → 4
    4.	0 → 3 → 4
Graph 7 Example

Algorithm

Here we use a recursive method to detect all the paths of a graph,

  1. We start the recursive function with the starting vertex.
  2. For each node
    1. Whenever we visited one vertex we mark it and go for all its unvisited adjacent nodes.
    2. If we found the destination vertex then count the number else we go for recursive call.
    Check(current node){
        visit[curr_node]=true;
        if(curr_node == destination){
            count++;
        }
        else{
            for( all the adjacent vertices ){
                if(not visited yet) then
                    check(adjacent vertex);
            }
        }
    }

C++ Implementation

#include <bits/stdc++.h>
using namespace std;

//Make a pair between vertex x and vertex y
void addedge(list<int>*ls,int x,int y){
	ls[x].push_back(y);
	ls[y].push_back(x);
}

//count the number of paths exists
void path_count(list<int>*ls,int s,int d,bool *visit,int &count){
	visit[s]=true;
	if(s==d){
		count++;
	}
	else{
		list<int>::iterator it;
		for(it=ls[s].begin();it!=ls[s].end();it++){
			if(!visit[*it]){
				path_count(ls,*it,d,visit,count);
			}
		}
	}
	visit[s]=false;
}

int main()
{
	list<int> ls[6];
	
	addedge(ls,0,1);
	addedge(ls,2,3);
	addedge(ls,3,4);
	addedge(ls,4,5);
	addedge(ls,1,2);
	addedge(ls,1,4);
	addedge(ls,3,0);
	
	bool visit[6];
	
	for(int i=0;i<6;i++){
		visit[i]=false;
	}
	
	int count=0;
	path_count(ls,0,4,visit,count);
	cout<<"Paths are : "<<count<<endl;
	
	return 0;
}

Output

Paths are : 4


Comments and Discussions!

Load comments ↻





Copyright © 2024 www.includehelp.com. All rights reserved.