Count total ways to reach destination from source in an undirected Graph | C ++ program to count total number of ways to reach destination in a graph ; Utility Function to count total ways ; Base condition When reach to the destination ; Make vertex visited ; Recursive function , for count ways ; Backtracking Make vertex unvisited ; Return total ways ; Function to count total ways to reach destination ; Loop to make all vertex unvisited , Initially ; Make source visited ; Print total ways
#include <iostream> NEW_LINE using namespace std ; int countWays ( int mtrx [ ] [ 11 ] , int vrtx , int i , int dest , bool visited [ ] ) { if ( i == dest ) { return 1 ; } int total = 0 ; for ( int j = 0 ; j < vrtx ; j ++ ) { if ( mtrx [ i ] [ j ] == 1 && ! visited [ j ] ) { visited [ j ] = true ; total += countWays ( mtrx , vrtx , j , dest , visited ) ; visited [ j ] = false ; } } return total ; } int totalWays ( int mtrx [ ] [ 11 ] , int vrtx , int src , int dest ) { bool visited [ vrtx ] ; for ( int i = 0 ; i < vrtx ; i ++ ) { visited [ i ] = false ; } visited [ src ] = true ; return countWays ( mtrx , vrtx , src , dest , visited ) ; } int main ( ) { int vrtx = 11 ; int mtrx [ 11 ] [ 11 ] = { { 0 , 1 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 0 } , { 1 , 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } , { 0 , 1 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } , { 0 , 1 , 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 , 0 , 1 , 0 , 0 , 0 , 1 , 0 } , { 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 1 , 0 } , { 1 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 , 0 } , { 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 , 0 } , { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 , 1 , 0 } , { 0 , 0 , 0 , 0 , 1 , 1 , 0 , 0 , 1 , 0 , 0 } , { 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 1 , 0 } } ; int src = 3 ; int dest = 9 ; cout << totalWays ( mtrx , vrtx , src - 1 , dest - 1 ) ; return 0 ; }