数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 打印从给定源到目标的所有路径
在这个问题中，我们给定了一个有向图，我们需要打印从图的源到目标的所有路径。
有向图是指边从顶点 a 指向顶点 b 的图。
让我们举个例子来理解这个问题
源 = K 目标 = P
输出
K -> T -> Y -> A -> P K -> T -> Y -> P K -> A -> P
在这里，我们找到了从 K 到 P 的路径。我们遍历了路径并打印了从 K 到 P 的所有路径。
为了解决这个问题，我们将使用深度优先搜索遍历技术遍历图。从源开始，我们将遍历存储在我们路径数组中的每个顶点，并将其标记为已访问（以避免多次访问同一个顶点）。当到达目标顶点时，打印此路径。
让我们看看实现该逻辑的程序 -
示例
#include<iostream>
#include <list>
using namespace std;
class Graph {
int V;
list<int> *adj;
void findNewPath(int , int , bool [], int [], int &);
public:
Graph(int V);
void addEdge(int u, int v);
void printPaths(int s, int d);
};
Graph::Graph(int V) {
this->V = V;
adj = new list<int>[V];
}
void Graph::addEdge(int u, int v) {
adj[u].push_back(v);
}
void Graph::printPaths(int s, int d) {
bool *visited = new bool[V];
int *path = new int[V];
int path_index = 0;
for (int i = 0; i < V; i++)
visited[i] = false;
findNewPath(s, d, visited, path, path_index);
}
void Graph::findNewPath(int u, int d, bool visited[],
int path[], int &path_index) {
visited[u] = true;
path[path_index] = u;
path_index++;
if (u == d) {
for (int i = 0; i<path_index; i++)
cout<<path[i]<<" ";
cout << endl;
} else {
list<int>::iterator i;
for (i = adj[u].begin(); i != adj[u].end(); ++i)
if (!visited[*i])
findNewPath(*i, d, visited, path, path_index);
}
path_index--;
visited[u] = false;
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(2, 0);
g.addEdge(2, 1);
g.addEdge(1, 3);
int s = 2, d = 3;
cout<<"Following are all different paths from source to destination : \n";
g.printPaths(s, d);
return 0;
}输出
Following are all different paths from source to destination : 2 0 1 3 2 0 3 2 1 3
更新于: 2020年1月16日
285 次浏览
广告