98. 所有可達路徑

98. 所有可達路徑

【題目描述】

給定一個有 n 個節點的有向無環圖，節點編號從 1 到 n。請編寫一個程序，找出并返回所有從節點 1 到節點 n 的路徑。每條路徑應以節點編號的列表形式表示。

【輸入描述】

第一行包含兩個整數 N，M，表示圖中擁有 N 個節點，M 條邊

后續 M 行，每行包含兩個整數 s 和 t，表示圖中的 s 節點與 t 節點中有一條路徑

【輸出描述】

輸出所有的可達路徑，路徑中所有節點的后面跟一個空格，每條路徑獨占一行，存在多條路徑，路徑輸出的順序可任意。

如果不存在任何一條路徑，則輸出 -1。

注意輸出的序列中，最后一個節點后面沒有空格！ 例如正確的答案是?1 3 5,而不是?1 3 5， 5后面沒有空格！

【輸入示例】

5 5
1 3
3 5
1 2
2 4
4 5

【輸出示例】

1 3 5
1 2 4 5  

?思路

深度優先搜索

深搜三部曲

1、確認遞歸函數，參數

首先dfs函數是對一個圖進行搜索，所以一定要存一個圖；還需要存當前處理的節點x；還需要存一個n表示終點。

還需要一些全局變量

一個res二維數組用來存所有的路徑也就是答案；一個path一維數組用來存單一路徑

（其實在遞歸函數的參數 不容易一開始就確定了，一般是在寫函數體的時候發現缺什么，參加就補什么）

2、確定終止條件

當目前遍歷的節點x 為 最后一個節點 n 的時候 就找到了一條 從出發點到終止點的路徑。

3、處理當前節點出發的路徑

首先要找到x節點指向了哪些節點

for (int i = 1; i <= n; i++) { // 遍歷節點x鏈接的所有節點if (graph[x][i] == 1) { // 找到 x指向的節點，就是節點i}
}

接下來將 選中的x所指向的節點，加入到路徑 path中

然后進入下一層遞歸

最后要注意回溯，撤銷添加節點的操作

輸出格式也需要注意

鄰接矩陣寫法

#include <iostream>
#include <vector>
using namespace std;
vector<vector<int>> result; // 收集符合條件的路徑
vector<int> path; // 1節點到終點的路徑void dfs (const vector<vector<int>>& graph, int x, int n) {// 當前遍歷的節點x 到達節點n if (x == n) { // 找到符合條件的一條路徑result.push_back(path);return;}for (int i = 1; i <= n; i++) { // 遍歷節點x鏈接的所有節點if (graph[x][i] == 1) { // 找到 x鏈接的節點path.push_back(i); // 遍歷到的節點加入到路徑中來dfs(graph, i, n); // 進入下一層遞歸path.pop_back(); // 回溯，撤銷本節點}}
}int main() {int n, m, s, t;cin >> n >> m;// 節點編號從1到n，所以申請 n+1 這么大的數組vector<vector<int>> graph(n + 1, vector<int>(n + 1, 0));while (m--) {cin >> s >> t;// 使用鄰接矩陣 表示無線圖，1 表示 s 與 t 是相連的graph[s][t] = 1;}path.push_back(1); // 無論什么路徑已經是從0節點出發dfs(graph, 1, n); // 開始遍歷// 輸出結果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}
}

鄰接表寫法

#include <iostream>
#include <vector>
#include <list>
using namespace std;vector<vector<int>> result; // 收集符合條件的路徑
vector<int> path; // 1節點到終點的路徑void dfs (const vector<list<int>>& graph, int x, int n) {if (x == n) { // 找到符合條件的一條路徑result.push_back(path);return;}for (int i : graph[x]) { // 找到 x指向的節點path.push_back(i); // 遍歷到的節點加入到路徑中來dfs(graph, i, n); // 進入下一層遞歸path.pop_back(); // 回溯，撤銷本節點}
}int main() {int n, m, s, t;cin >> n >> m;// 節點編號從1到n，所以申請 n+1 這么大的數組vector<list<int>> graph(n + 1); // 鄰接表while (m--) {cin >> s >> t;// 使用鄰接表 ，表示 s -> t 是相連的graph[s].push_back(t);}path.push_back(1); // 無論什么路徑已經是從0節點出發dfs(graph, 1, n); // 開始遍歷// 輸出結果if (result.size() == 0) cout << -1 << endl;for (const vector<int> &pa : result) {for (int i = 0; i < pa.size() - 1; i++) {cout << pa[i] << " ";}cout << pa[pa.size() - 1]  << endl;}
}