什麼是由DFS該曲線

Question

該曲線使用DFS中，節點按照下面的順序訪問，得到溶液路徑（多於一個的後繼節點，節點推到「前沿「按字母順序）：

S-> A-> E-> D-> F-」G

那是探視序列的溶液路徑藏漢？如果是這樣，爲什麼它不是S-> A-> E-> G，因爲G也是E的後繼節點？ PS：我新算法，所以如果我明顯不理解這個概念，請讓我知道。

Answer 1

如果您正在訪問節點，DFS方法將根據鄰接列表的創建順序遍歷圖形。

例如，將節點E的繼任者可能會在以下方面的順序：

1- E-> D, G 
2- E-> G, D 

在第一種方式，你將穿越D->F->G或D->G直接在這兩種情況下，你將訪問節點G在遍歷節點E其他後繼節點之前，因此您將無法遍歷路徑S->A->E->G，因爲節點G將在節點D或F之前被訪問過。

在第二種方式中，你會直接穿越E->G，所以這將導致遍歷路徑S->A->E->G，而且還因爲它會從節點E將已經訪問過你將無法從節點D或F訪問節點G 。

如果您使用true或false訪問前一個場景，但如果您嘗試使用邊緣成本查找最短路徑，那麼您將需要使用Dijkstra的算法來查找最短路徑圖表，如果你不熟悉它，你可以閱讀更多關於here的信息。

Answer 2

我假設它考慮啓發式和邊緣成本來確定下一個要訪問的節點。

在的IT着眼於它的三種可能性開始：

A = 9 + 13 = 21 
B = 14 + 14 = 28 
C = 15 + 15 = 30 

然後選擇一個，並期待在距其僅可用的路徑，並進入E.

給E，我們有兩種可能性：

D = 2 + 8 = 10 
G = 19 + 0 = 19 

它將然後選擇d，現在有兩種可能性：

F = 11 + 5 = 16 
G = 16 + 0 = 16 

其領帶等等取決於算法是如何設置它，你給解決它去到F，然後有兩種可能性：

E = 6 + 7 = 13 
G = 6 + 0 = 6 

然後去G和最後它會看到這是目標節點並返回狀態序列。