BFS和術語「訪問」的正確性

mark x as visited 
list L = x 
tree T = x 
while L nonempty 
    choose some vertex v from front of list 
    process v 
    for each unmarked neighbor w 
     mark w as visited 
     add it to end of list 
     add edge vw to T

大多數代碼將選擇在訪問它們之前將相鄰節點標記爲已訪問。首先添加所有鄰居並稍後再訪問它會不會在技術上正確？BFS和術語「訪問」的正確性

list L = x 
tree T = x 
while L nonempty 
    choose some vertex v from front of list 
    if (V NOT YET VISITD) 
     MARK V AS VISITED HERE 
     for each unmarked neighbor w 
      add it to end of list 
      add edge vw to T

爲什麼每個BFS似乎都會將節點標記爲已訪問，而您甚至沒有訪問它們呢？我正試圖爲BFS找到一個理論上正確的代碼。哪一個是正確的？

來源

2016-11-12 Zanko

兩者都是正確的，但它們使用了visited這個詞的不同定義。算法有很多變化，並且有許多不同的實現都是正確的，BFS就是一個例子。

來源

2016-11-13 00:01:45

這兩種算法都可以工作，但第二個版本可能將兩個相同的節點添加到列表L中兩次。這不會影響正確性，因爲附加檢查是否訪問了節點，但會增加內存消耗並需要額外檢查。這就是爲什麼你通常會看到教科書中的第一個算法。

來源

2016-11-13 00:07:52 nwellnhof

回覆：「第二個版本可能會向列表L添加兩次相同的節點」：或者兩次以上。在極端的情況下，如果圖是一個帶* n *頂點的完整圖，那麼一個頂點將被添加一次，一次兩次，一次三次等等，一直向上通過添加的一個頂點（* n * - 1 ）次。所以一個在頂點數量上應該是線性的算法是二次的。 – ruakh

@ruakh沒錯，但這只是空間的複雜性而已。完整圖的時間複雜度始終是頂點數的二次方，因爲邊的數量已經是二次的。 – nwellnhof

好點。（想想看，對於每個未標記的鄰居w'位必須真正意味着'對於每個鄰居w'加上'如果w未被標記'）。 – ruakh

BFS和術語「訪問」的正確性

回答

相關問題