數(shù)據(jù)結(jié)構(gòu)–圖（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）（Java）

數(shù)據(jù)結(jié)構(gòu)–圖（深度優(yōu)先遍歷和廣度優(yōu)先遍歷）（Java）

博客說明

文章所涉及的資料來自互聯(lián)網(wǎng)整理和個人總結(jié)，意在于個人學(xué)習(xí)和經(jīng)驗匯總，如有什么地方侵權(quán)，請聯(lián)系本人刪除，謝謝！

圖的常用概念

圖是一種數(shù)據(jù)結(jié)構(gòu)，其中結(jié)點可以具有零個或多個相鄰元素。兩個結(jié)點之間的連接稱為邊。 結(jié)點也可以稱為頂點。

  • 頂點(vertex)
  • 邊(edge)
  • 路徑
  • 無向圖
image-20200904124205865
  • 有向圖
image-20200904124318805
  • 帶權(quán)圖
image-20200904124332489

圖的表示方式

圖的表示方式有兩種：二維數(shù)組表示（鄰接矩陣）；鏈表表示（鄰接表）。

鄰接矩陣

鄰接矩陣是表示圖形中頂點之間相鄰關(guān)系的矩陣，對于n個頂點的圖而言，矩陣是的row和col表示的是1....n個點。

image-20200904124501028
鄰接表

鄰接矩陣需要為每個頂點都分配n個邊的空間，其實有很多邊都是不存在,會造成空間的一定損失

鄰接表的實現(xiàn)只關(guān)心存在的邊，不關(guān)心不存在的邊。因此沒有空間浪費，鄰接表由數(shù)組+鏈表組成

image-20200904124627030

代碼實現(xiàn)

package com.guizimo;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;

public class Graph {

    private ArrayList<String> vertexList; 
    private int[][] edges; 
    private int numOfEdges; 
    private boolean[] isVisited;
    
    public static void main(String[] args) {

        int n = 8;
        String Vertexs[] = {"1", "2", "3", "4", "5", "6", "7", "8"};
        Graph graph = new Graph(n);
        for(String vertex: Vertexs) {
            graph.insertVertex(vertex);
        }
        
        //插入圖的節(jié)點
        graph.insertEdge(0, 1, 1);
        graph.insertEdge(0, 2, 1);
        graph.insertEdge(1, 3, 1);
        graph.insertEdge(1, 4, 1);
        graph.insertEdge(3, 7, 1);
        graph.insertEdge(4, 7, 1);
        graph.insertEdge(2, 5, 1);
        graph.insertEdge(2, 6, 1);
        graph.insertEdge(5, 6, 1);

        //遍歷圖
        graph.showGraph();
        
        System.out.println("廣度優(yōu)先遍歷
        graph.dfs(); 
        System.out.println("深度優(yōu)先遍歷
        graph.bfs();
        
    }
    
    public Graph(int n) {
        edges = new int[n][n];
        vertexList = new ArrayList<String>(n);
        numOfEdges = 0;
    }
    

    public int getFirstNeighbor(int index) {
        for(int j = 0; j < vertexList.size(); j++) {
            if(edges[index][j] > 0) {
                return j;
            }
        }
        return -1;
    }

    public int getNextNeighbor(int v1, int v2) {
        for(int j = v2 + 1; j < vertexList.size(); j++) {
            if(edges[v1][j] > 0) {
                return j;
            }
        }
        return -1;
    }
    
    //深度優(yōu)先遍歷
    private void dfs(boolean[] isVisited, int i) {
        System.out.print(getValueByIndex(i) + "->");
        isVisited[i] = true;
        int w = getFirstNeighbor(i);
        while(w != -1) {
            if(!isVisited[w]) {
                dfs(isVisited, w);
            }
            w = getNextNeighbor(i, w);
        }
        
    }
    
    public void dfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                dfs(isVisited, i);
            }
        }
    }
    
    //廣度優(yōu)先遍歷
    private void bfs(boolean[] isVisited, int i) {
        int u ; 
        int w ; 
        LinkedList queue = new LinkedList();
        System.out.print(getValueByIndex(i) + "=>");
        isVisited[i] = true;
        queue.addLast(i);
        
        while( !queue.isEmpty()) {
            u = (Integer)queue.removeFirst();
            w = getFirstNeighbor(u);
            while(w != -1) {
                if(!isVisited[w]) {
                    System.out.print(getValueByIndex(w) + "=>");
                    isVisited[w] = true;
                    queue.addLast(w);
                }
                w = getNextNeighbor(u, w); 
            }
        }
        
    } 
    
    public void bfs() {
        isVisited = new boolean[vertexList.size()];
        for(int i = 0; i < getNumOfVertex(); i++) {
            if(!isVisited[i]) {
                bfs(isVisited, i);
            }
        }
    }
    
    public int getNumOfVertex() {
        return vertexList.size();
    }
                       
    //遍歷
    public void showGraph() {
        for(int[] link : edges) {
            System.err.println(Arrays.toString(link));
        }
    }
                       
    public int getNumOfEdges() {
        return numOfEdges;
    }

    public String getValueByIndex(int i) {
        return vertexList.get(i);
    }
                       
    public int getWeight(int v1, int v2) {
        return edges[v1][v2];
    }
                       
    //添加鄰接矩陣
    public void insertVertex(String vertex) {
        vertexList.add(vertex);
    }
    
  //插入權(quán)值
    public void insertEdge(int v1, int v2, int weight) {
        edges[v1][v2] = weight;
        edges[v2][v1] = weight;
        numOfEdges++;
    }
}

圖的深度優(yōu)先搜索(Depth First Search)

深度優(yōu)先遍歷，從初始訪問結(jié)點出發(fā)，初始訪問結(jié)點可能有多個鄰接結(jié)點，深度優(yōu)先遍歷的策略就是首先訪問第一個鄰接結(jié)點，然后再以這個被訪問的鄰接結(jié)點作為初始結(jié)點，訪問它的第一個鄰接結(jié)點， 可以這樣理解：每次都在訪問完當(dāng)前結(jié)點后首先訪問當(dāng)前結(jié)點的第一個鄰接結(jié)點

算法
  • 訪問初始結(jié)點v，并標(biāo)記結(jié)點v為已訪問。
  • 查找結(jié)點v的第一個鄰接結(jié)點w。
  • 若w存在，則繼續(xù)執(zhí)行4，如果w不存在，則回到第1步，將從v的下一個結(jié)點繼續(xù)。
  • 若w未被訪問，對w進(jìn)行深度優(yōu)先遍歷遞歸（即把w當(dāng)做另一個v，然后進(jìn)行步驟123）。
  • 查找結(jié)點v的w鄰接結(jié)點的下一個鄰接結(jié)點，轉(zhuǎn)到步驟3
代碼
//深度優(yōu)先遍歷
private void dfs(boolean[] isVisited, int i) {
  System.out.print(getValueByIndex(i) + "->");
  isVisited[i] = true;
  int w = getFirstNeighbor(i);
  while(w != -1) {
    if(!isVisited[w]) {
      dfs(isVisited, w);
    }
    w = getNextNeighbor(i, w);
  }

}

public void dfs() {
  isVisited = new boolean[vertexList.size()];
  for(int i = 0; i < getNumOfVertex(); i++) {
    if(!isVisited[i]) {
      dfs(isVisited, i);
    }
  }
}

圖的廣度優(yōu)先搜索(Broad First Search)

類似于一個分層搜索的過程，廣度優(yōu)先遍歷需要使用一個隊列以保持訪問過的結(jié)點的順序，以便按這個順序來訪問這些結(jié)點的鄰接結(jié)點

算法
  • 訪問初始結(jié)點v并標(biāo)記結(jié)點v為已訪問。
  • 結(jié)點v入隊列
  • 當(dāng)隊列非空時，繼續(xù)執(zhí)行，否則算法結(jié)束。
  • 出隊列，取得隊頭結(jié)點u。
  • 查找結(jié)點u的第一個鄰接結(jié)點w。
  • 若結(jié)點u的鄰接結(jié)點w不存在，則轉(zhuǎn)到步驟3；否則循環(huán)執(zhí)行以下三個步驟：
    • 若結(jié)點w尚未被訪問，則訪問結(jié)點w并標(biāo)記為已訪問。
    • 結(jié)點w入隊列
    • 查找結(jié)點u的繼w鄰接結(jié)點后的下一個鄰接結(jié)點w，轉(zhuǎn)到步驟6
代碼
//廣度優(yōu)先遍歷
private void bfs(boolean[] isVisited, int i) {
  int u ; 
  int w ; 
  LinkedList queue = new LinkedList();
  System.out.print(getValueByIndex(i) + "=>");
  isVisited[i] = true;
  queue.addLast(i);

  while( !queue.isEmpty()) {
    u = (Integer)queue.removeFirst();
    w = getFirstNeighbor(u);
    while(w != -1) {
      if(!isVisited[w]) {
        System.out.print(getValueByIndex(w) + "=>");
        isVisited[w] = true;
        queue.addLast(w);
      }
      w = getNextNeighbor(u, w); 
    }
  }

} 

public void bfs() {
  isVisited = new boolean[vertexList.size()];
  for(int i = 0; i < getNumOfVertex(); i++) {
    if(!isVisited[i]) {
      bfs(isVisited, i);
    }
  }
}

感謝

尚硅谷

以及勤勞的自己，個人博客，GitHub

微信公眾號
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

友情鏈接更多精彩內(nèi)容