Dado un grafo no dirigido , un vértice de origen ‘s’ y un vértice de destino ‘d’ , la tarea es contar los caminos totales desde el ‘s’ dado hasta la ‘d’ .
Ejemplos
Entrada: s = 1, d = 4
Salida: 2
Explicación:
A continuación se muestran los 2 caminos del 1 al 4
1 -> 3 -> 4
1 -> 2 -> 3 -> 4Entrada: s = 3, d = 9
Salida: 6
Explicación:
A continuación se muestran los 6 caminos del 3 al 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
Enfoque:
la idea es hacer un recorrido en profundidad primero de un gráfico no dirigido dado.
- Comience el recorrido desde la fuente.
- Siga almacenando los vértices visitados en una array que dice ‘visitado []’.
- Si llegamos al vértice de destino, incrementamos la cuenta en ‘1’.
- Lo importante es marcar los vértices actuales en visited[] como visitados para que el recorrido no vaya en ciclos.
A continuación se muestra la implementación del enfoque anterior:
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>
Producción:
6
Análisis de rendimiento :
- Complejidad de tiempo : en el enfoque anterior, para un vértice dado, verificamos todos los vértices, por lo que la complejidad de tiempo es O (N * N) donde N no es ningún vértice.
- Complejidad del espacio auxiliar : en el enfoque anterior, estamos utilizando una array visitada de tamaño N donde N es el número de vértices, por lo que la complejidad del espacio auxiliar es O(N) .
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA