摘要: 簡單說一下回溯法，回溯跟深度優先遍歷是分不開的，我們傾向于把回溯看做深度優先遍歷的延伸。我們知道，圖的深度優先遍歷每個節點只會被訪問一次，因為我們一旦走過一個點，我們就會做相應的標記，避免重復經過同一個點。而回溯的做法是，當走過某一個點時，標記走過，并把該點壓棧；當該節點出棧時，我們再把它標記為沒有走過，這樣就能保證另外一條路也能經過該點了
閱讀全文
posted @
2012-08-20 16:09 小鼠標 閱讀(458) |
評論 (0) |
編輯 收藏
摘要: 圖的常見遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，他們的作用是將圖中的每個點都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長都相等（比如都是1）的話，深度優先遍歷的過程是：
1.任意選定一個點p0作為遍歷的起點
2.從未訪問節點中任選一個距離p0最近的點進行訪問，并標記該點被訪問過
3.重復第2步，直到該連通分支中的所有節點都被訪問過
閱讀全文
posted @
2012-08-20 12:23 小鼠標 閱讀(1607) |
評論 (0) |
編輯 收藏