Count total ways to reach destination from source in an undirected Graph

0 0 10 minutes read

Given an undirected graph, a source vertex ‘s’ and a destination vertex ‘d’, the task is to count the total paths from the given ‘s’ to ‘d’.

Examples

Input: s = 1, d = 4

Output: 2
Explanation:
Below are the 2 paths from 1 to 4
1 -> 3 -> 4
1 -> 2 -> 3 -> 4

Input: s = 3, d = 9

Output: 6
Explanation:
Below are the 6 paths from 3 to 9
3 -> 2 -> 1 -> 7 -> 6 -> 5 -> 10 -> 9
3 -> 2 -> 1 -> 7 -> 6 -> 10 -> 9
3 -> 2 -> 1 -> 7 -> 8 -> 9
3 -> 4 -> 2 -> 1 -> 7 -> 6 -> 5 -> 10 -> 9
3 -> 4 -> 2 -> 1 -> 7 -> 6 -> 10 -> 9
3 -> 4 -> 2 -> 1 -> 7 -> 8 -> 9

Approach:
The idea is to do Depth First Traversal of a given undirected graph.

Start the traversal from the source.
Keep storing the visited vertices in an array saying ‘visited[]’.
If we reach the destination vertex, increment the count by ‘1’.
The important thing is to mark current vertices in visited[] as visited so that the traversal doesn’t go in cycles.

Below is the implementation of the above approach:

C

#include <stdio.h>
#include <stdbool.h>
 
// Utility Function to count total ways
int countWays(int mtrx[][11], int vrtx,
            int i, int dest, bool visited[])
{
    // Base condition
    // When reach to the destination
    if (i == dest) {
        return 1;
    }
 
    int total = 0;
    for (int j = 0; j < vrtx; j++) {
        if (mtrx[i][j] == 1 && !visited[j]) {
 
            // Make vertex visited
            visited[j] = true;
 
            // Recursive function, for count ways
            total += countWays(mtrx, vrtx, j, dest, visited);
 
            // Backtracking
            // Make vertex unvisited
            visited[j] = false;
        }
    }
 
    // Return total ways
    return total;
}
 
// Function to count total ways
// to reach destination
int totalWays(int mtrx[][11], int vrtx,
            int src, int dest)
{
    bool visited[vrtx];
 
    // Loop to make all vertex unvisited,
    // Initially
    for (int i = 0; i < vrtx; i++) {
        visited[i] = false;
    }
 
    // Make source visited
    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;
 
// Print total ways
printf("%d\n", totalWays(mtrx, vrtx, src, dest));
 
return 0;
}

C++

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

Java

// Java program to count total number of
// ways to reach destination in a graph
class GFG{
  
// Utility Function to count total ways
static int countWays(int mtrx[][], int vrtx,
              int i, int dest, boolean visited[])
{
    // Base condition
    // When reach to the destination
    if (i == dest) {
  
        return 1;
    }
    int total = 0;
    for (int j = 0; j < vrtx; j++) {
        if (mtrx[i][j] == 1 && !visited[j]) {
  
            // Make vertex visited
            visited[j] = true;
  
            // Recursive function, for count ways
            total += countWays(mtrx, vrtx,
                               j, dest, visited);
  
            // Backtracking
            // Make vertex unvisited
            visited[j] = false;
        }
    }
  
    // Return total ways
    return total;
}
  
// Function to count total ways
// to reach destination
static int totalWays(int mtrx[][], int vrtx,
              int src, int dest)
{
    boolean []visited = new boolean[vrtx];
  
    // Loop to make all vertex unvisited,
    // Initially
    for (int i = 0; i < vrtx; i++) {
        visited[i] = false;
    }
  
    // Make source visited
    visited[src] = true;
  
    return countWays(mtrx, vrtx, src, dest,
                     visited);
}
  
public static void main(String[] args)
{
    int vrtx = 11;
    int mtrx[][] = {
        { 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;
  
    // Print total ways
    System.out.print(totalWays(mtrx, vrtx, src - 1,
                      dest - 1));
  
}
}
 
// This code contributed by Rajput-Ji

Python 3

# Python 3 program to count total number of
# ways to reach destination in a graph
 
# Utility Function to count total ways
def countWays(mtrx, vrtx, i, dest, visited):
     
    # Base condition
    # When reach to the destination
    if (i == dest):
        return 1
         
    total = 0
    for j in range(vrtx):
        if (mtrx[i][j] == 1 and not visited[j]):
 
            # Make vertex visited
            visited[j] = True;
 
            # Recursive function, for count ways
            total += countWays(mtrx, vrtx, j, dest, visited);
 
            # Backtracking
            # Make vertex unvisited
            visited[j] = False;
 
    # Return total ways
    return total
 
# Function to count total ways
# to reach destination
def totalWays(mtrx, vrtx, src, dest):
    visited = [False]*vrtx
 
    # Loop to make all vertex unvisited,
    # Initially
    for i in range(vrtx):
        visited[i] = False
 
    # Make source visited
    visited[src] = True;
 
    return countWays(mtrx, vrtx, src, dest,visited)
 
# Driver function
vrtx = 11
mtrx = [
        [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 ]
    ]
 
src = 3
dest = 9
 
# Print total ways
print(totalWays(mtrx, vrtx, src - 1,dest - 1))
 
# This code is contributed by atul kumar shrivastava

C#

// C# program to count total number of
// ways to reach destination in a graph
using System;
 
class GFG{
   
// Utility Function to count total ways
static int countWays(int[,] mtrx, int vrtx,
              int i, int dest, bool[] visited)
{
    // Base condition
    // When reach to the destination
    if (i == dest) {
   
        return 1;
    }
    int total = 0;
    for (int j = 0; j < vrtx; j++) {
        if (mtrx[i,j] == 1 && !visited[j]) {
   
            // Make vertex visited
            visited[j] = true;
   
            // Recursive function, for count ways
            total += countWays(mtrx, vrtx,
                               j, dest, visited);
   
            // Backtracking
            // Make vertex unvisited
            visited[j] = false;
        }
    }
   
    // Return total ways
    return total;
}
   
// Function to count total ways
// to reach destination
static int totalWays(int[,] mtrx, int vrtx,
              int src, int dest)
{
    bool[]visited = new bool[vrtx];
   
    // Loop to make all vertex unvisited,
    // Initially
    for (int i = 0; i < vrtx; i++) {
        visited[i] = false;
    }
   
    // Make source visited
    visited[src] = true;
   
    return countWays(mtrx, vrtx, src, dest,
                     visited);
}
   
public static void Main()
{
    int vrtx = 11;
    int[,] mtrx = {
        { 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;
   
    // Print total ways
    Console.Write(totalWays(mtrx, vrtx, src - 1,
                      dest - 1));
   
}
}

Javascript

<script>
// Javascript program to count total number of
// ways to reach destination in a graph
 
// Utility Function to count total ways
function countWays(mtrx,vrtx,i,dest,visited)
{
    // Base condition
    // When reach to the destination
    if (i == dest) {
    
        return 1;
    }
    let total = 0;
    for (let j = 0; j < vrtx; j++) {
        if (mtrx[i][j] == 1 && !visited[j]) {
    
            // Make vertex visited
            visited[j] = true;
    
            // Recursive function, for count ways
            total += countWays(mtrx, vrtx,
                               j, dest, visited);
    
            // Backtracking
            // Make vertex unvisited
            visited[j] = false;
        }
    }
    
    // Return total ways
    return total;
}
 
// Function to count total ways
// to reach destination
function totalWays(mtrx,vrtx,src,dest)
{
    let visited = new Array(vrtx);
    
    // Loop to make all vertex unvisited,
    // Initially
    for (let i = 0; i < vrtx; i++) {
        visited[i] = false;
    }
    
    // Make source visited
    visited[src] = true;
    
    return countWays(mtrx, vrtx, src, dest,
                     visited);
}
 
let vrtx = 11;
let mtrx=[
        [ 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 ]
    ];
     
let src = 3;
let dest = 9;
// Print total ways
document.write(totalWays(mtrx, vrtx, src - 1,
                      dest - 1));
// This code is contributed by avanitrachhadiya2155
</script>

Output:

Performance Analysis:

Time Complexity: In the above approach, for a given vertex, we check all vertices, so the worst case time complexity is O(N²) where N is no of vertices.
Auxiliary Space Complexity: In the above approach, we are using a visited array of size N where N is the number of vertices, so Auxiliary space complexity is O(N).

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!