Imprima todas las rutas desde un origen determinado hasta un destino utilizando BFS

Dado un gráfico dirigido, un vértice de origen ‘src’ y un vértice de destino ‘dst’, imprime todas las rutas desde el ‘src’ dado hasta el ‘dst’.

Considere el siguiente gráfico dirigido. Deje que src sea 2 y dst sea 3. Hay 3 caminos diferentes de 2 a 3.

Ya hemos discutido Imprimir todas las rutas desde un origen dado a un destino usando DFS .

A continuación se muestra la solución basada en BFS.

Algoritmo:  

create a queue which will store path(s) of type vector
initialise the queue with first path starting from src

Now run a loop till queue is not empty
   get the frontmost path from queue
   check if the lastnode of this path is destination
       if true then print the path
   run a loop for all the vertices connected to the
   current vertex i.e. lastnode extracted from path
      if the vertex is not visited in current path
         a) create a new path from earlier path and 
             append this vertex
         b) insert this new path to queue

Implementación:

// C++ program to print all paths of source to
// destination in given graph
#include <bits/stdc++.h>
using namespace std;
 
// utility function for printing
// the found path in graph
void printpath(vector<int>& path)
{
    int size = path.size();
    for (int i = 0; i < size; i++)
        cout << path[i] << " ";   
    cout << endl;
}
 
// utility function to check if current
// vertex is already present in path
int isNotVisited(int x, vector<int>& path)
{
    int size = path.size();
    for (int i = 0; i < size; i++)
        if (path[i] == x)
            return 0;
    return 1;
}
 
// utility function for finding paths in graph
// from source to destination
void findpaths(vector<vector<int> >&g, int src,
                                 int dst, int v)
{
    // create a queue which stores
    // the paths
    queue<vector<int> > q;
 
    // path vector to store the current path
    vector<int> path;
    path.push_back(src);
    q.push(path);
    while (!q.empty()) {
        path = q.front();
        q.pop();
        int last = path[path.size() - 1];
 
        // if last vertex is the desired destination
        // then print the path
        if (last == dst)
            printpath(path);       
 
        // traverse to all the nodes connected to
        // current vertex and push new path to queue
        for (int i = 0; i < g[last].size(); i++) {
            if (isNotVisited(g[last][i], path)) {
                vector<int> newpath(path);
                newpath.push_back(g[last][i]);
                q.push(newpath);
            }
        }
    }
}
 
// driver program
int main()
{
    vector<vector<int> > g;
    // number of vertices
    int v = 4;
    g.resize(4);
 
    // construct a graph
    g[0].push_back(3);
    g[0].push_back(1);
    g[0].push_back(2);
    g[1].push_back(3);
    g[2].push_back(0);
    g[2].push_back(1);
 
    int src = 2, dst = 3;
    cout << "path from src " << src
         << " to dst " << dst << " are \n";
 
    // function for finding the paths
    findpaths(g, src, dst, v);
 
    return 0;
}

// Java program to print all paths of source to
// destination in given graph
import java.io.*;
import java.util.*;
 
class Graph{
 
// utility function for printing
// the found path in graph
private static void printPath(List<Integer> path)
{
    int size = path.size();
    for(Integer v : path)
    {
        System.out.print(v + " ");
    }
    System.out.println();
}
 
// Utility function to check if current
// vertex is already present in path
private static boolean isNotVisited(int x,
                                    List<Integer> path)
{
    int size = path.size();
    for(int i = 0; i < size; i++)
        if (path.get(i) == x)
            return false;
             
    return true;
}
 
// Utility function for finding paths in graph
// from source to destination
private static void findpaths(List<List<Integer> > g,
                              int src, int dst, int v)
{
     
    // Create a queue which stores
    // the paths
    Queue<List<Integer> > queue = new LinkedList<>();
 
    // Path vector to store the current path
    List<Integer> path = new ArrayList<>();
    path.add(src);
    queue.offer(path);
     
    while (!queue.isEmpty())
    {
        path = queue.poll();
        int last = path.get(path.size() - 1);
 
        // If last vertex is the desired destination
        // then print the path
        if (last == dst)
        {
            printPath(path);
        }
 
        // Traverse to all the nodes connected to
        // current vertex and push new path to queue
        List<Integer> lastNode = g.get(last);
        for(int i = 0; i < lastNode.size(); i++)
        {
            if (isNotVisited(lastNode.get(i), path))
            {
                List<Integer> newpath = new ArrayList<>(path);
                newpath.add(lastNode.get(i));
                queue.offer(newpath);
            }
        }
    }
}
 
// Driver code
public static void main(String[] args)
{
    List<List<Integer> > g = new ArrayList<>();
    int v = 4;
    for(int i = 0; i < 4; i++)
    {
        g.add(new ArrayList<>());
    }
 
    // Construct a graph
    g.get(0).add(3);
    g.get(0).add(1);
    g.get(0).add(2);
    g.get(1).add(3);
    g.get(2).add(0);
    g.get(2).add(1);
    int src = 2, dst = 3;
    System.out.println("path from src " + src +
                       " to dst " + dst + " are ");
                        
    // Function for finding the paths                  
    findpaths(g, src, dst, v);
}
}
 
// This code is contributed by rajatsri94

# Python3 program to print all paths of
# source to destination in given graph
from typing import List
from collections import deque
 
# Utility function for printing
# the found path in graph
def printpath(path: List[int]) -> None:
     
    size = len(path)
    for i in range(size):
        print(path[i], end = " ")
         
    print()
 
# Utility function to check if current
# vertex is already present in path
def isNotVisited(x: int, path: List[int]) -> int:
 
    size = len(path)
    for i in range(size):
        if (path[i] == x):
            return 0
             
    return 1
 
# Utility function for finding paths in graph
# from source to destination
def findpaths(g: List[List[int]], src: int,
              dst: int, v: int) -> None:
                   
    # Create a queue which stores
    # the paths
    q = deque()
 
    # Path vector to store the current path
    path = []
    path.append(src)
    q.append(path.copy())
     
    while q:
        path = q.popleft()
        last = path[len(path) - 1]
 
        # If last vertex is the desired destination
        # then print the path
        if (last == dst):
            printpath(path)
 
        # Traverse to all the nodes connected to
        # current vertex and push new path to queue
        for i in range(len(g[last])):
            if (isNotVisited(g[last][i], path)):
                newpath = path.copy()
                newpath.append(g[last][i])
                q.append(newpath)
 
# Driver code
if __name__ == "__main__":
     
    # Number of vertices
    v = 4
    g = [[] for _ in range(4)]
 
    # Construct a graph
    g[0].append(3)
    g[0].append(1)
    g[0].append(2)
    g[1].append(3)
    g[2].append(0)
    g[2].append(1)
 
    src = 2
    dst = 3
    print("path from src {} to dst {} are".format(
        src, dst))
 
    # Function for finding the paths
    findpaths(g, src, dst, v)
 
# This code is contributed by sanjeev2552

// C# program to print all paths of source to
// destination in given graph
 
using System;
using System.Collections.Generic;
 
public class Graph{
 
// utility function for printing
// the found path in graph
static void printPath(List<int> path)
{
    int size = path.Count;
    foreach(int v in path)
    {
        Console.Write(v + " ");
    }
    Console.WriteLine();
}
 
// Utility function to check if current
// vertex is already present in path
static bool isNotVisited(int x, List<int> path)
{
    int size = path.Count;
    for(int i = 0; i < size; i++)
        if (path[i] == x)
            return false;
             
    return true;
}
 
// Utility function for finding paths in graph
// from source to destination
private static void findpaths(List<List<int> > g,
                              int src, int dst, int v)
{
     
    // Create a queue which stores
    // the paths
    Queue<List<int> > queue = new Queue<List<int>>();
 
    // Path vector to store the current path
    List<int> path = new List<int>();
    path.Add(src);
    queue.Enqueue(path);
     
    while (queue.Count!=0)
    {
        path = queue.Dequeue();
        int last = path[path.Count - 1];
 
        // If last vertex is the desired destination
        // then print the path
        if (last == dst)
        {
            printPath(path);
        }
 
        // Traverse to all the nodes connected to
        // current vertex and push new path to queue
        List<int> lastNode = g[last];
        for(int i = 0; i < lastNode.Count; i++)
        {
            if (isNotVisited(lastNode[i], path))
            {
                List<int> newpath = new List<int>(path);
                newpath.Add(lastNode[i]);
                queue.Enqueue(newpath);
            }
        }
    }
}
 
// Driver code
public static void Main(String[] args)
{
    List<List<int> > g = new List<List<int>>();
    int v = 4;
    for(int i = 0; i < 4; i++)
    {
        g.Add(new List<int>());
    }
 
    // Construct a graph
    g[0].Add(3);
    g[0].Add(1);
    g[0].Add(2);
    g[1].Add(3);
    g[2].Add(0);
    g[2].Add(1);
    int src = 2, dst = 3;
    Console.WriteLine("path from src " + src +
                       " to dst " + dst + " are ");
                        
    // Function for finding the paths                  
    findpaths(g, src, dst, v);
}
}
 
// This code is contributed by shikhasingrajput

path from src 2 to dst 3 are 
2 0 3 
2 1 3 
2 0 1 3 

Este artículo es una contribución de Mandeep Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.