登入
首頁 所有文章 資料結構 圖形結構-深度優先與廣度優先搜尋之介紹與範例
長也   2018-12-06 20:01:51(11個月前)    887點閱   0喜歡  0收藏
圖形結構-深度優先與廣度優先搜尋之介紹與範例  

在上一篇文章"圖形結構-基本介紹與表示方法"已經介紹過兩種圖形結構在電腦中的表示方法,本文將介紹如何走訪已經建立好的圖形。

DFS(Depth first search)深度優先搜尋

又稱縱向優先搜尋,其拜訪順序為:(1)拜訪起點V,(2)拜訪V鄰近尚未被拜訪的節點W,(3)若有任一節點鄰近的節點皆被訪問,就回到最近曾被拜訪過的節點,(4)若任何已經走過的節點鄰近的節點皆已被拜訪過,代表走訪結束。

深度優先搜尋是以堆疊(遞迴)實作,以下舉例解釋其運作方式:

 

 

  1. 先輸出V1(V1為起點)

  2. 將V1鄰近的點V2, V3放入堆疊當中

    V2
    V3

     

  3. 彈出V2,將相鄰的V1, V4, V5加入堆疊當中。(備註:由於V1已經被訪問過,故實作時不會將V1放入堆疊)

    V1
    V4
    V5
    V3

     

  4. 彈出V1,由於V1已經被輸出,再彈出V4,並將V4鄰近的V2、V8放入堆疊

    V2
    V8
    V5
    V3


  5. 彈出V2,由於V2已經被輸出,再彈出V8,並將V8鄰近的V4、V5、V10放入堆疊

    V4
    V5
    V10
    V5
    V3

     

  6. 彈出V4,由於V4已被輸出,再彈出V5,並將V5相鄰的V2、V8放入堆疊

    V2
    V8
    V10
    V5
    V3

     

  7. 彈出V2,V2已被輸出,再彈出V8,V8已被輸出,再彈出V10,將V10相鄰的V8、V9放入堆疊

    V8
    V9
    V5
    V3

     

  8. 彈出V8,V8已被輸出,再彈出V9,將V9相鄰的V6、V7、V10放入堆疊

    V6
    V7
    V10
    V5
    V3

     

  9. 彈出V6,將V6相鄰的V3、V9放入堆疊

    V3
    V9
    V7
    V10
    V5
    V3

     

  10. 彈出V3,將V3相鄰的V1、V6、V7放入堆疊

    V1
    V6
    V7
    V9
    V7
    V10
    V5
    V3

     

  11. 彈出V1,V1已被輸出,再彈出V6,V6已被輸出,再彈出V7,將V7相鄰的V3、V9放入堆疊

    V3
    V9
    V9
    V7
    V10
    V5
    V3

     

  12. 最後彈出堆疊所有的內容,這些彈出的頂點皆已被輸出,故堆疊已經,代表搜尋完成。

由上述步驟,我們可以得到: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。

廣度優先是以佇列來完成,範例以迴圈實作。其運作方式如下:

  1. 拜訪起點V1,並將V1相鄰的V2、V3放入佇列

    V1 V2 V3


  2. 拜訪V2,將V2相鄰的V4、V5放入佇列(V1已被拜訪,故不放入)

    V1 V2 V3 V4 V5


  3. 拜訪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;
                
            }
            
        }
        
    }

結論

  1. DFS會先拜訪鄰近而尚未被拜訪的節點,若所有鄰近節點都已被拜訪,則會回到曾經已被拜訪的節點。

  2. BFS會先拜訪完所有鄰近的節點,才會往下一階度走訪。

  3. DFS以堆疊(遞迴)實作。

  4. BFS以佇列(迴圈)實作。

  5. 在二元樹的走訪中,前、中、後序也屬於DFS深度優先搜尋。

本文作者:長也

糾結與想不開的資管系學生,之前常碰PHP,現在常碰到的是Python,閒暇之餘就記錄一些筆記。

             

如要發表回覆,請先 登入

  0則回覆