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 -> 4Input: 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 waysint 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 destinationint 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 waysprintf("%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 waysint 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 destinationint 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 graphclass GFG{ // Utility Function to count total waysstatic 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 destinationstatic 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 waysdef 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 destinationdef 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 functionvrtx = 11mtrx = [ [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 = 3dest = 9# Print total waysprint(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 graphusing System;class GFG{ // Utility Function to count total waysstatic 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 destinationstatic 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 waysfunction 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 destinationfunction 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 waysdocument.write(totalWays(mtrx, vrtx, src - 1, dest - 1));// This code is contributed by avanitrachhadiya2155</script> |
Output:
6
Performance Analysis:
- Time Complexity: In the above approach, for a given vertex, we check all vertices, so the worst case time complexity is O(N2) 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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
