28 圖、圖的存儲、圖的深度優先周遊和廣度優先周遊

圖

文章目錄

• 圖
• • 1. 圖基本介紹
  • • 1.1 為什麼要有圖
    • 1.2 圖的舉例說明
    • 1.3 圖的常用概念
  • 2. 圖的表示方式
  • • 2.1 鄰接矩陣
    • 2.2 鄰接表
  • 3. 圖的鄰接矩陣存儲方式的代碼實作
  • 4. 圖的深度優先周遊
  • • 4.1 步驟
    • 4.2 代碼實作
  • 5. 圖的廣度優先周遊
  • • 5.1 步驟
    • 5.2 代碼實作

1. 圖基本介紹

1.1 為什麼要有圖

1. 線性表局限于一個直接前驅和一個直接後繼的關系。
2. 樹也隻能有一個直接前驅也就是父節點。
3. 當我們需要表示多對多的關系時， 這裡我們就用到了圖。

1.2 圖的舉例說明

1. 圖是一種資料結構，其中結點可以具有零個或多個相鄰元素。兩個結點之間的連接配接稱為邊。 結點也可以稱為頂點。

   

1.3 圖的常用概念

1. 頂點
2. 邊
3. 路徑
4. 無向圖

   

5. 有向圖
6. 帶權圖

   

2. 圖的表示方式

1. 圖的表示方式有兩種：二維數組表示（鄰接矩陣）；連結清單表示（鄰接表）。

2.1 鄰接矩陣

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

   

2.2 鄰接表

1. 鄰接矩陣需要為每個頂點都配置設定 n 個邊的空間，其實有很多邊都是不存在,會造成空間的一定損失。
2. 鄰接表的實作隻關心存在的邊，不關心不存在的邊。是以沒有空間浪費，鄰接表由數組+連結清單組成。

   

3. 圖的鄰接矩陣存儲方式的代碼實作

package com.guli.graph;

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

public class GraphDemo {
    public static void main(String[] args) {
        String[] vertexs = {"A", "B", "C", "D", "E"};
        // 建立圖
        Graph graph = new Graph(5);
        // 給圖中插入頂點
        for (String vertex : vertexs) {
            graph.insertVertex(vertex);
        }
        // 給圖添加邊  A-B A-C B-C B-D B-E
        graph.insertEdge("A", "B", 1);
        graph.insertEdge("A", "C", 1);
        graph.insertEdge("B", "C", 1);
        graph.insertEdge("B", "D", 1);
        graph.insertEdge("B", "E", 1);

        // 輸出圖的鄰接矩陣
        graph.showAdjacencyMatrix();
    }

}

class Graph {
    private ArrayList<String> vertexs;
    private int[][] edges;
    private int numOfEdges;

    /**
     * 初始化圖
     *
     * @param numOfVertex 頂點個數
     */
    public Graph(int numOfVertex) {
        vertexs = new ArrayList<>(numOfVertex);
        edges = new int[numOfVertex][numOfVertex];
        numOfEdges = 0;
    }

    /**
     * 插入頂點
     *
     * @param vertex 頂點
     */
    public void insertVertex(String vertex) {
        vertexs.add(vertex);
    }

    /**
     * 插入邊
     *
     * @param v1     頂點1
     * @param v2     頂點2
     * @param weight 兩點之間的權重
     */
    public void insertEdge(String v1, String v2, int weight) {
        int index1 = vertexs.indexOf(v1);
        int index2 = vertexs.indexOf(v2);
        edges[index1][index2] = weight;
        edges[index2][index1] = weight;
        numOfEdges++;
    }

    /**
     * 傳回邊的條數
     *
     * @return 邊的條數
     */
    public int getNumOfEdges() {
        return numOfEdges;
    }

    /**
     * 傳回頂點的個數
     *
     * @return 頂點的個數
     */
    public int getNumOfVertexs() {
        return vertexs.size();
    }

    /**
     * 輸出圖的鄰接矩陣
     */
    public void showAdjacencyMatrix() {
        for (int[] edge : edges) {
            System.out.println(Arrays.toString(edge));
        }
    }
}
           

4. 圖的深度優先周遊

4.1 步驟

1. 通路初始結點 v，并标記結點 v 為已通路。
2. 查找結點 v 的第一個鄰接結點 w。
3. 若 w 存在，則繼續執行 4，如果 w 不存在，則回到第 1 步，将從 v 的下一個結點繼續。
4. 若 w 未被通路，對 w 進行深度優先周遊遞歸（即把 w 當做另一個 v，然後進行步驟 123）。
5. 查找結點 v 的 w 鄰接結點的下一個鄰接結點，轉到步驟 3。

4.2 代碼實作

/**
     * 尋找第一個與目前頂點鄰接的未被通路過的節點的下标
     *
     * @param vertex 目前節點
     * @return 第一個與目前頂點鄰接的未被通路過的節點的下标
     */
    private int getFirstNeighbor(String vertex) {
        // 得到目前節點的下标
        int index = vertexs.indexOf(vertex);
        // 尋找第一個與目前頂點鄰接的未被通路過的節點的下标
        for (int i = 0; i < edges[0].length; i++) {
            if (edges[index][i] > 0 && !isVisited.contains(vertexs.get(i))) {
                return i;
            }
        }
        return -1;
    }

    /**
     * 圖的深度優先周遊
     *
     * @param startVertex 開始周遊的節點
     */
    public ArrayList<String> dfs(String startVertex) {
        isVisited = new ArrayList<>();
        // 存放最終序列
        ArrayList<String> seq = new ArrayList<>();
        // 記錄指向要擷取鄰接節點的節點的下标
        int temp = 0;
        seq.add(startVertex);
        // 記錄通路過的節點
        isVisited.add(startVertex);
        int num = 0;
        // 得到序列
        while (seq.size() < vertexs.size()) {
            // 尋找第一個與目前頂點鄰接的未被通路過的節點的下标,并将節點存放進最終序列中
            if ((num = getFirstNeighbor(seq.get(temp))) != -1) {
                seq.add(vertexs.get(num));
                isVisited.add(vertexs.get(num));
                temp = seq.size() - 1;
            } else {
                temp--;
            }
        }
        return seq;
    }
           

5. 圖的廣度優先周遊

5.1 步驟

1. 通路初始結點 v 并标記結點 v 為已通路。
2. 結點 v 入隊列。
3. 當隊列非空時，繼續執行，否則算法結束。
4. 出隊列，取得隊頭結點 u。
5. 查找結點 u 的所有未被通路過的鄰接結點，并入隊列。
6. 循環執行 456。

5.2 代碼實作

/**
     * 獲得所有與目前頂點鄰接且未被通路過的頂點
     *
     * @param vertex 目前頂點
     * @return 所有與目前頂點鄰接且未被通路過的頂點
     */
    private ArrayList<String> getAllNeighbor(String vertex) {
        ArrayList<String> list = new ArrayList<>();
        int index = vertexs.indexOf(vertex);
        for (int i = 0; i < edges.length; i++) {
            if (edges[index][i] > 0 && !isVisited.contains(vertexs.get(i))) {
                list.add(vertexs.get(i));
            }
        }
        return list;
    }

    /**
     * 圖的廣度優先周遊
     *
     * @param startVertex 開始周遊的節點
     * @return 最終序列
     */
    public ArrayList<String> bfs(String startVertex) {
        isVisited = new ArrayList<>();
        // 存放最終序列
        ArrayList<String> seq = new ArrayList<>();
        // 臨時存放部分節點
        Queue<String> queue = new LinkedList<>();
        queue.add(startVertex);
        isVisited.add(startVertex);
        while (seq.size() < vertexs.size() && !queue.isEmpty()) {
            String v = queue.remove();
            seq.add(v);
            queue.addAll(getAllNeighbor(v));
            isVisited.addAll(getAllNeighbor(v));
        }
        return seq;
    }