搜尋此網誌

2011年8月13日 星期六

Graph Traversal --Java

基本作法要先把圖的資料存放成adjacent list
然後把每一筆list排序
把sample input排序後的資料要長成這樣
0:1 4 5
1:0 2 4
2:1 3
3:2 4
4:0 1 3
5:0
接著用queue來儲存breadth first
寬度優先所以要先把最前面列所有的資料存起來,只要不是root,也還沒visit過就可以存
然後逐次往後面的列重複去做.


用stack來儲存depth first的資料
因為是深度優先,所以要把每一列非root的第一筆資料存起來.只要不是root,也還沒visit過就可以存


input data:
1
6 7
0 1
0 5
4 3
2 3
0 4
1 4
2 1

source code: