在上一篇文章"圖形結構-基本介紹與表示方法"已經介紹過兩種圖形結構在電腦中的表示方法,本文將介紹如何走訪已經建立好的圖形。
又稱縱向優先搜尋,其拜訪順序為:(1)拜訪起點V,(2)拜訪V鄰近尚未被拜訪的節點W,(3)若有任一節點鄰近的節點皆被訪問,就回到最近曾被拜訪過的節點,(4)若任何已經走過的節點鄰近的節點皆已被拜訪過,代表走訪結束。
深度優先搜尋是以堆疊(遞迴)實作,以下舉例解釋其運作方式:
V2 |
V3 |
V1 |
V4 |
V5 |
V3 |
V2 |
V8 |
V5 |
V3 |
V4 |
V5 |
V10 |
V5 |
V3 |
V2 |
V8 |
V10 |
V5 |
V3 |
V8 |
V9 |
V5 |
V3 |
V6 |
V7 |
V10 |
V5 |
V3 |
V3 |
V9 |
V7 |
V10 |
V5 |
V3 |
V1 |
V6 |
V7 |
V9 |
V7 |
V10 |
V5 |
V3 |
V3 |
V9 |
V9 |
V7 |
V10 |
V5 |
V3 |
由上述步驟,我們可以得到:V1,V2,V4,V8,V5,V10,V9,V6,V3,V7的走訪順序,但這個順序並非唯一,必須視放入堆疊的順序。
另外值得一提的是,在"樹—二元樹的介紹與走訪"一文中所介紹的前、中、後序走訪,也是屬於一種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,
又稱橫向優先搜尋,與深度優先不同的是:廣度優先會先走訪所有鄰近的節點,才會往下一階度走訪。如本文上方範例,其走訪之結果為:V1, V2, V3, V4, V5, V6, V7, V8, V9, V10。
廣度優先是以佇列來完成,範例以迴圈實作。其運作方式如下:
V1 | V2 | V3 |
V1 | V2 | V3 | V4 | V5 |
V1 | V2 | V3 | V4 | V5 | V6 | V7 | V8 |
以此類推,最後可以得知拜訪順序為:V1, V2, V3, V4, V5, V6, V7, V8, V9, V10。
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;
}
}
}
關於作者
粉絲專頁
文章分類