回溯深度第一搜索算法僞代碼

boolean backtrackDFS(v) { 
    If (SolutionFound(v)) return true; 
    Mark vertex v as reached. 
    for (each unreached vertex u adjacenct from v) 
     if (backtrakDFS(u)) return true; 
    Unmark vertex v; 
    return false; 
}

這裏爲什麼需要Unmark vertex v？以及爲什麼添加這樣的行是安全的，因此v再次被取消，是否會導致重新訪問？回溯深度第一搜索算法僞代碼

來源

2011-05-17 colinfang

我不認爲這是必要的。解開你所做的事，通常只是一個很好的做法，並且保持你找到它們時的樣子。

例如，包括該行將允許您使用相同的功能多次搜索，而無需單獨的操作來清除標記。

來源

2011-05-17 11:09:25 sje397

爲什麼添加這樣的行是安全的，因此v再次被重新獲取，會導致重新訪問嗎？ – colinfang 2011-05-17 11:30:45

@colinfang：不行，直到所有連接的分支都被探測完畢，纔會調用該行，所以在沒有重新訪問的機會之前它不會被清除。 – sje397 2011-05-17 11:33:52

回溯深度第一搜索算法僞代碼

回答

相關問題