poj1273--網絡流
摘要: 最赤裸的網絡流，不斷找出增廣路增廣即可。找增廣路時，這里用的深度優先搜索。
閱讀全文
posted @
2012-09-07 21:29 小鼠標 閱讀(302) |
評論 (1) 編輯
poj2488--回溯
摘要: 簡單說一下回溯法，回溯跟深度優先遍歷是分不開的，我們傾向于把回溯看做深度優先遍歷的延伸。我們知道，圖的深度優先遍歷每個節點只會被訪問一次，因為我們一旦走過一個點，我們就會做相應的標記，避免重復經過同一個點。而回溯的做法是，當走過某一個點時，標記走過，并把該點壓棧；當該節點出棧時，我們再把它標記為沒有走過，這樣就能保證另外一條路也能經過該點了
閱讀全文
posted @
2012-08-20 16:09 小鼠標 閱讀(469) |
評論 (0) 編輯
poj2386--圖的遍歷
摘要: 圖的常見遍歷方式有兩種：深度優先遍歷和廣度優先遍歷，他們的作用是將圖中的每個點都訪問一遍，只不過是順序不同。
如果把圖中的每條邊長都相等（比如都是1）的話，深度優先遍歷的過程是：
1.任意選定一個點p0作為遍歷的起點
2.從未訪問節點中任選一個距離p0最近的點進行訪問，并標記該點被訪問過
3.重復第2步，直到該連通分支中的所有節點都被訪問過
閱讀全文
posted @
2012-08-20 12:23 小鼠標 閱讀(1619) |
評論 (0) 編輯
zoj1060，poj1094--拓撲排序
摘要: 下面我先說以下拓撲排序：
嚴蔚敏《數據結構》上的定義是：由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓撲排序。
直觀的說偏序指集合中僅有部分成員之間可比較，而全序指集合中全體成員之間均可比較。
拓撲排序的具體做法是：
1.在有向圖中選擇一個沒有前驅（入度為0）的頂點，輸出
2.從圖中刪除該頂點和所有以它為尾的弧，并更新相關點的入度
3.重復1，2步，直到所有頂點都被輸出，或者發現圖中存在回路。
閱讀全文
posted @
2012-08-16 19:19 小鼠標 閱讀(1824) |
評論 (0) 編輯
單源最短路徑Dijkstra算法
摘要: dijkstra算法是解決單源最短路徑問題的經典算法，具有O(N^2)的時間復雜度（N為節點個數），這種算法采用的是貪心策略，它與最小生成樹的Prim算法極其相似，這兩種算法僅僅是cost[]代表的含義不同……
閱讀全文
posted @
2012-08-08 16:27 小鼠標 閱讀(1892) |
評論 (0) 編輯