在雙向圖中檢查節點 A 和節點 B 之間是否存在路徑。
我的代碼不適用于某些輸入（下面提供了示例）。這個實作是正確的還是我錯過了什么？
bool[] visited = null;
public bool ValidPath(int n, int[][] edges, int start, int end) {
IList<int>[] adjacencyList = new List<int>[n];
visited = new bool[n];
// create adjacency list
for(int i = 0; i < edges.Length; i ){
int a = edges[i][0];
int b = edges[i][1];
if(adjacencyList[a] == null)
adjacencyList[a] = new List<int>();
adjacencyList[a].Add(b);
if(adjacencyList[b] == null)
adjacencyList[b] = new List<int>();
adjacencyList[b].Add(a);
}
return DFS(adjacencyList, start, end);
}
private bool DFS(IList<int>[] adjacencyList, int start, int end){
if(start == end) return true;
if(!visited[start]){
visited[start] = true;
foreach(var v in adjacencyList[start]){
if(v == end) return true;
if(!visited[v])
DFS(adjacencyList, v, end);
}
}
return false;
}
這適用于以下示例：
輸入：n = 3，edges = [[0,1],[1,2],[2,0]]，start = 0，end = 2 輸出：true
輸入：n = 6，edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], start = 0, end = 5 輸出：false
不適用于以下（預期回傳值為真，但我得到假）：
輸入：10，邊 = [[4,3],[1,4],[4,8],[1,7],[6,4],[4,2],[7,4],[ 4,0],[0,9],[5,4]], 開始 = 5, 結束 = 9
uj5u.com熱心網友回復：
該方法是正確的，唯一的問題是在 recursive 內部DFS，您需要跟蹤所有后續DFS呼叫的結果。如果任何遞回呼叫回傳 true，則解決方案應回傳 true（而不是直接回傳 false）。這是該DFS功能的略微修改版本：
private bool DFS(IList<int>[] adjacencyList, int start, int end){
if(start == end) return true;
bool status = false;
if(!visited[start]){
visited[start] = true;
foreach(var v in adjacencyList[start]){
if(v == end) {
return true;
}
if(!visited[v]) {
status = status || DFS(adjacencyList, v, end);
}
}
}
return status;
}
更新：
感謝評論中的建議。如果DFS對于任何相鄰頂點回傳true，則該方法可以直接回傳true（而不是DFS呼叫其他相鄰頂點并保留那個status）。這給了我們另一個變體DFS：
private bool DFS(IList<int>[] adjacencyList, int start, int end){
if (start == end) return true;
bool status = false;
if(!visited[start]){
visited[start] = true;
foreach(var v in adjacencyList[start]){
if(v == end) {
return true;
}
if(!visited[v] && DFS(adjacencyList, v, end)) {
return true;
}
}
}
return status;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/403883.html
標籤：
下一篇：如何從register.cshtml和register.cshtml.cs中的AspNetRoles表構建下拉串列？