圖形結構－深度優先與廣度優先搜尋之介紹與範例
2018-12-06 20:01:51 資料結構
在上一篇文章＂圖形結構－基本介紹與表示方法＂已經介紹過兩種圖形結構在電腦中的表示方法，本文將介紹如何走訪已經建立好的圖形。
DFS(Depth first search)深度優先搜尋
又稱縱向優先搜尋，其拜訪順序為：(1)拜訪起點V，(2)拜訪V鄰近尚未被拜訪的節點W，(3)若有任一節點鄰近的節點皆被訪問，就回到最近曾被拜訪過的節點，(4)若任何已經走過的節點鄰近的節點皆已被拜訪過，代表走訪結束。
深度優先搜尋是以堆疊（遞迴）實作，以下舉例解釋其運作方式：
- 先輸出V1(V1為起點)
- 將V1鄰近的點V2, V3放入堆疊當中
V2 V3 - 彈出V2，將相鄰的V1, V4, V5加入堆疊當中。(備註：由於V1已經被訪問過，故實作時不會將V1放入堆疊)
V1 V4 V5 V3 - 彈出V1，由於V1已經被輸出，再彈出V4，並將V4鄰近的V2、V8放入堆疊
V2 V8 V5 V3 - 彈出V2，由於V2已經被輸出，再彈出V8，並將V8鄰近的V4、V5、V10放入堆疊
V4 V5 V10 V5 V3 - 彈出V4，由於V4已被輸出，再彈出V5，並將V5相鄰的V2、V8放入堆疊
V2 V8 V10 V5 V3 - 彈出V2，V2已被輸出，再彈出V8，V8已被輸出，再彈出V10，將V10相鄰的V8、V9放入堆疊
V8 V9 V5 V3 - 彈出V8，V8已被輸出，再彈出V9，將V9相鄰的V6、V7、V10放入堆疊
V6 V7 V10 V5 V3 - 彈出V6，將V6相鄰的V3、V9放入堆疊
V3 V9 V7 V10 V5 V3 - 彈出V3，將V3相鄰的V1、V6、V7放入堆疊
V1 V6 V7 V9 V7 V10 V5 V3 - 彈出V1，V1已被輸出，再彈出V6，V6已被輸出，再彈出V7，將V7相鄰的V3、V9放入堆疊
V3 V9 V9 V7 V10 V5 V3 - 最後彈出堆疊所有的內容，這些彈出的頂點皆已被輸出，故堆疊已經，代表搜尋完成。
由上述步驟，我們可以得到：V1，V2，V4，V8，V5，V10，V9，V6，V3，V7的走訪順序，但這個順序並非唯一，必須視放入堆疊的順序。
另外值得一提的是，在"樹—二元樹的介紹與走訪"一文中所介紹的前、中、後序走訪，也是屬於一種DFS，而前、中、後序也以堆疊實作。
DFS的實作
實作上，我們輸入以下相鄰矩陣的資料，檔名為dfs.txt：
10
0 1 1 0 0 0 0 0 0 0
1 0 0 1 1 0 0 0 0 0
1 0 0 0 0 1 1 0 0 0
0 1 0 0 0 0 0 1 0 0
0 1 0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0 1 0
0 0 1 0 0 0 0 0 1 0
0 0 0 1 1 0 0 0 0 1
0 0 0 0 0 1 1 0 0 1
0 0 0 0 0 0 0 1 1 0並將其整理成相鄰串列後，以遞迴的方式走訪，但要注意的是，實作上會跳過已經走訪的節點，已經走訪過的節點不會再加入堆疊(呼叫遞迴)。以下為程式碼：
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
/**
*
* @author hazuya
*/
class node{
int v;
node link;
}
class DFStest {
final static int maxVer = 100; //最大節點數
node node = new node();
node lastnode = new node();
static node[] adjlist = new node[maxVer + 1]; //相鄰串列
static boolean[] visit = new boolean[maxVer + 1]; //紀錄是否已被走訪
static int totalVer = 0;
public void buildAdj(){
int vi = 0, vj = 0, weight = 0; //節點V(i, j) 以及 路徑之權重
Scanner input = null;
try{
input = new Scanner(new FileInputStream("dfs.txt")); //讀入資料檔
}catch(FileNotFoundException e){ //接取檔案讀取錯誤例外
System.out.print("dfs.txt not found.");
System.exit(1); //離開程式
}
totalVer = input.nextInt(); //總結點數量
//建立串列首與預設尚未走訪
for(vi = 1; vi <= totalVer; vi++){
visit[vi] = false; //預設尚未走訪
adjlist[vi] = new node(); //建立串列首
adjlist[vi].v = vi; //節點
adjlist[vi].link = null;
}
//讀取節點
for(vi = 1; vi <= totalVer; vi++){
for(vj = 1; vj <= totalVer; vj++){
weight = input.nextInt(); //取得V(i,j)路徑權重
if(weight != 0){ //如果V(i,j)權重不為0，則加入串列
node = new node();
node.v = vj; //節點
lastnode = searchlast(adjlist[vi]); //將其串入相鄰串列的後面
lastnode.link = node;
}
}
}
input.close();
}
//列出相鄰串列
public void showAdj(){
node ptr = new node();
System.out.println("Head adjacencyNode");
System.out.println("=========================");
for(int index = 1; index <= totalVer; index++){
System.out.printf("V%d ", adjlist[index].v);
ptr = adjlist[index].link;
while(ptr != null){
System.out.printf("=>V%d ", ptr.v);
ptr = ptr.link;
}
System.out.println();
}
}
//進行DFS走訪
public void dfs(int v){
node ptr = new node();
System.out.printf("V%d, ", adjlist[v].v); //輸出節點
visit[v] = true; //節點已訪問
ptr = adjlist[v].link; //訪問鄰近節點
while(ptr != null){
if(visit[ptr.v] != true) //當鄰近節點沒被訪問時就去訪問，遞迴呼叫dfs函式
dfs(ptr.v);
else
ptr = ptr.link; //已被訪問就略過
}
}
//尋找串列末端
public node searchlast(node ll){
node ptr = new node();
ptr = ll;
while(ptr.link != null){
ptr = ptr.link;
}
return ptr;
}
//主函數
public static void main(String[] args) {
DFStest dfs = new DFStest();
dfs.buildAdj();
dfs.showAdj();
dfs.dfs(1);
}
}
輸入dfs.txt後，輸出結果為：
Head adjacencynode1
=========================
V1 =>V2 =>V3
V2 =>V1 =>V4 =>V5
V3 =>V1 =>V6 =>V7
V4 =>V2 =>V8
V5 =>V2 =>V8
V6 =>V3 =>V9
V7 =>V3 =>V9
V8 =>V4 =>V5 =>V10
V9 =>V6 =>V7 =>V10
V10 =>V8 =>V9
V1, V2, V4, V8, V5, V10, V9, V6, V3, V7, BFS（breadth first search）廣度優先搜尋
又稱橫向優先搜尋，與深度優先不同的是：廣度優先會先走訪所有鄰近的節點，才會往下一階度走訪。如本文上方範例，其走訪之結果為：V1, V2, V3, V4, V5, V6, V7, V8, V9, V10。
廣度優先是以佇列來完成，範例以迴圈實作。其運作方式如下：
- 拜訪起點V1，並將V1相鄰的V2、V3放入佇列
V1 V2 V3 - 拜訪V2，將V2相鄰的V4、V5放入佇列(V1已被拜訪，故不放入)
V1 V2 V3 V4 V5 - 拜訪V3，將V3相鄰的V6、V7放入佇列(V1已被拜訪，故不放入)
V1 V2 V3 V4 V5 V6 V7 V8
以此類推，最後可以得知拜訪順序為：V1, V2, V3, V4, V5, V6, V7, V8, V9, V10。
BFS的實作
BFS實作以迴圈實作，輸入的檔案一樣為上方的dfs.txt，而不同的只有走訪的函式不同，BFS的走訪函式如下：
//進行BFS走訪
public void bfs(int v){
Node2 ptr = new Node2();
for(int vi = v; vi<=totalVer; vi++){
ptr = adjlist[vi];
while(ptr != null){
if(visit[ptr.v] != true){
System.out.printf("V%d, ", ptr.v);
visit[ptr.v] = true;
}
ptr = ptr.link;
}
}
}
結論
- DFS會先拜訪鄰近而尚未被拜訪的節點，若所有鄰近節點都已被拜訪，則會回到曾經已被拜訪的節點。
- BFS會先拜訪完所有鄰近的節點，才會往下一階度走訪。
- DFS以堆疊(遞迴)實作。
- BFS以佇列(迴圈)實作。
- 在二元樹的走訪中，前、中、後序也屬於DFS深度優先搜尋。
