資料結構
網路
關係資料庫管理系統
作業系統
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 次瀏覽
廣告