我試圖通過下圖找到所有路徑：
start
/ \
c--A-----b--d
\ /
end
它只是非回圈的，因為具有小寫名稱的頂點只能被訪問一次，例如d不應該訪問頂點，因為要將它包含在通過圖的路徑中，頂點b必須被訪問兩次。
圖中所有允許的路徑是：
start,A,b,A,c,A,end
start,A,b,A,end
start,A,b,end
start,A,c,A,b,A,end
start,A,c,A,b,end
start,A,c,A,end
start,A,end
start,b,A,c,A,end
start,b,A,end
start,b,end
幾乎我所有的谷歌結果都是有向圖的，我能找到的讓它們適用于我的無向圖的唯一方法是將每條邊添加兩次，每個方向一次，我認為這比我目前的，非作業的還要混亂解決方案。
我想出的最好的方法是嘗試通過圖進行遞回遍歷：
private HashSet<List<Edge>> paths = new();
private List<Edge> _path = new();
HashSet<Vertex> smallsVisited = new HashSet<Vertex>();
private void Traverse(Vertex start)
{
var traverseEnd = GetVertexByName("end");
if (start == traverseEnd)
{
paths.Add(_path.ToList());
_path.Clear();
return;
}
if (smallsVisited.Contains(start))
return;
if (start.Name != "start" && char.IsLower(start.Name[0]))
smallsVisited.Add(start);
var traverseStart = GetVertexByName("start");
var neighbours = _adjacencyList[start].Where(v => v != traverseStart);
foreach (var end in neighbours)
{
_path.Add(new Edge(start, end));
Traverse(end);
}
}
我Traverse用被呼叫的頂點呼叫start來設定程序滾動。當引數start是指定的頂點時，我希望遍歷停止，end但結果只是一個單一的路徑，即 vertex startto vertex b。
我很新，只有幾天，處理圖表，并且在遞回方面非常生疏。我究竟做錯了什么？
uj5u.com熱心網友回復：
這是我如何處理遞回遍歷這個。我已將圖形設定為頂點名稱字典到鄰居串列。此外，由于“開始”以小寫字符開頭，因此我只是依靠它讓它不會通過該頂點回傳。這里的另一個技巧是將路徑傳遞到當前頂點，以便您可以在每次遞回中構建它，但每個遞回都不會受到其他遞回的影響。并且由于您有路徑，您可以檢查它是否包含小寫頂點。另請注意，我們仍然可以根據圖表獲得無限路徑和 StackOverflow。例如，如果您的圖表將“b”更改為“B”，那么您可以在“A”和“B”之間移動無數次，而此代碼不會以任何方式檢測到。
void Main()
{
var graph = new Dictionary<string, List<string>>
{
["start"] = new List<string>{"A", "b"},
["A"] = new List<string>{"c", "b", "end", "start"},
["b"] = new List<string>{"A", "d", "end", "start"},
["c"] = new List<string>{"A"},
["d"] = new List<string>{"b"},
["end"] = new List<string>{"A", "b"},
};
var result = Traverse(graph, "start", "end");
foreach(var x in result)
{
Console.WriteLine(string.Join("-", x));
}
}
public static IEnumerable<IEnumerable<string>> Traverse(
Dictionary<string, List<string>> graph,
string current,
string end,
IEnumerable<string> path = null)
{
// Initialize the path if we don't have one yet.
path ??= Enumerable.Empty<string>();
// Do not allow the path to go to a lower cast vertex
// more than once.
if(char.IsLower(current[0]) && path.Contains(current))
{
yield break;
}
path = path.Append(current);
// If we are at the end then return the path and break.
if(current == end)
{
yield return path;
yield break;
}
// Find all the paths from the current vertex through
// each of it's neighbors and return them.
foreach(var neighbor in graph[current])
{
foreach(var subPath in Traverse(graph, neighbor, end, path))
{
yield return subPath;
}
}
}
結果是
start-A-c-A-b-A-end
start-A-c-A-b-end
start-A-c-A-end
start-A-b-A-c-A-end
start-A-b-A-end
start-A-b-end
start-A-end
start-b-A-c-A-end
start-b-A-end
start-b-end
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/388364.html
上一篇：Python超出遞回限制