原文:
给定一个有向图、一个源顶点“src”和一个目标顶点“dst”，打印从给定“src”到“dst”的所有路径。
考虑下面的有向图。假设 src 为 2，dst 为 3。从 2 到 3 有 3 种不同的路径。
我们已经讨论过 打印从给定源到目的地的所有路径。 下面是基于 bfs 的pg电子试玩链接的解决方案。
算法:
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
c
// c program to print all paths of source to
// destination in given graph
#include
using namespace std;
// utility function for printing
// the found path in graph
void printpath(vector& 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& 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 >&g, int src,
int dst, int v)
{
// create a queue which stores
// the paths
queue > q;
// path vector to store the current path
vector 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 newpath(path);
newpath.push_back(g[last][i]);
q.push(newpath);
}
}
}
}
// driver program
int main()
{
vector > 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 语言(一种计算机语言，尤用于创建网站)
// 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 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 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 > g,
int src, int dst, int v)
{
// create a queue which stores
// the paths
queue > queue = new linkedlist<>();
// path vector to store the current path
list 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 lastnode = g.get(last);
for(int i = 0; i < lastnode.size(); i )
{
if (isnotvisited(lastnode.get(i), path))
{
list newpath = new arraylist<>(path);
newpath.add(lastnode.get(i));
queue.offer(newpath);
}
}
}
}
// driver code
public static void main(string[] args)
{
list > 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
python 3
# 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
输出:
path from src 2 to dst 3 are
2 0 3
2 1 3
2 0 1 3
本文由 供稿。如果你喜欢 geeksforgeeks 并想投稿，你也可以使用写一篇文章或者把你的文章邮寄到 contribute@geeksforgeeks.org。看到你的文章出现在极客博客pg电子试玩链接主页上，帮助其他极客。 如果发现有不正确的地方，或者想分享更多关于上述话题的信息，请写评论。
麻将胡了pg电子网站的版权属于：月萌api www.moonapi.com，转载请注明出处
