我正在嘗試實作深度優先搜索（DFS），如果圖中兩個節點之間存在路徑，則使用遞回回傳布林值。下面是我的實作。邊緣輸入采用向量陣列的形式。
我嘗試除錯程式以檢測我到底哪里出錯了，但我不知道為什么在檢查節點是否被訪問后呼叫return validPath_helper(n, i, destination, visited, adjList);函式中的函式時它會給出分段錯誤。validPath
bool validPath_helper(int n, int source, int destination, vector<bool> visited, vector<vector<int>> adjList){
visited[source] = true;
if(adjList[source][destination]){
return true;
}
for(int i=0; i<adjList[source].size(); i ){
if(adjList[source][i]){
return validPath_helper(n, i, destination, visited, adjList);
}
}
return false;
}
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
vector<bool> visited(n, false);
vector<vector<int>> adjList(n);
int u, v;
for(int i=0; i<edges.size(); i ){
u = edges[i][0];
v = edges[i][1];
adjList[u].push_back(v);
adjList[v].push_back(u);
}
for(int i=source; i<n; i ){
if(!visited[i]){
return validPath_helper(n, i, destination, visited, adjList);
}
}
return false;
}
任何幫助，將不勝感激！
uj5u.com熱心網友回復：
段錯誤通常是由于訪問未分配的記憶體而發生的，因此您應該首先調查。你說的validPath_helper是觸發了段錯誤，所以你應該檢查那個功能。
在您的情況下，罪魁禍首是這一行：
if(adjList[source][destination]){
return true;
}
在這里，您想檢查源節點和目標節點之間是否存在邊。但是，如果您回顧一下您是如何創建鄰接串列的，您會發現它是一個向量向量，對于每個節點，我們都有一個與它有邊的節點串列。
例如下圖：
1 - 2
0 - 1
1 - 3
鄰接串列將是：
0 -> 1
1 -> 0 2 3
2 -> 1
3 -> 1
讓我們以源 2 和目標 3 為例。現在當你validPath_helper被呼叫時，它會檢查adjList[2][3]，但正如你在上面看到的 adjList[2] 的長度只有 1，所以沒有要檢查的第 4 個元素（3 是索引，所以第 4 個元素）。這是您的段錯誤的原因。
這也會導致您的代碼中出現一個完全不同的問題，您想檢查邊緣是否存在于 2 和 3 之間，但您檢查的是 2 串列的第 4 位是否存在非零元素。
您可以通過多種方式解決此問題。
方式#1
代替
if(adjList[source][destination]){
return true;
}
嘗試
for (int index = 0; index < adjList[source].size(); index ) {
if (adjList[source][index] == destination)
return true;
}
您需要在validPath_helper函式的兩個位置進行此更改。
方式#2
在大圖的情況下，上述方法會增加程式的運行時間，如果您關心運行時間并了解哈希串列，則此方法更好。
#include <unordered_set> // at top
bool validPath_helper(int n, int source, int destination, vector<bool> visited, vector<unordered_set<int>> adjList){
visited[source] = true;
if(adjList[source].find(destination) != adjList[source].end()){
return true;
}
for(int i: adjList[source]){
if (!visited[i] && validPath_helper(n, i, destination, visited, adjList)) {
return true;
}
}
return false;
}
bool validPath(int n, vector<vector<int>>& edges, int source, int destination) {
vector<bool> visited(n, false);
vector<unordered_set<int>> adjList(n);
int u, v;
for(int i=0; i<edges.size(); i ){
u = edges[i][0];
v = edges[i][1];
adjList[u].insert(v);
adjList[v].insert(u);
}
return validPath_helper(n, i, destination, visited, adjList);
}
您的代碼中還有幾個錯誤：
- Some unnecessary loops in both your functions.
- You set visited to true but do not check it before calling DFS on new nodes.
- You return the first DFS result and don't check other child nodes. (Due to return validPath_helper call in validPath_helper function.
Look into these issues too, refer to way # 2 above if you are stuck.
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/437637.html