數(shù)據(jù)結構與算法--圖的實現(xiàn)（鄰接表、鄰接矩陣、邊的數(shù)組）

數(shù)據(jù)結構與算法--圖的實現(xiàn)（鄰接表、鄰接矩陣、邊的數(shù)組）

應該用哪種數(shù)據(jù)結構實現(xiàn)圖呢？主要有如下三種：

鄰接矩陣

對一個擁有V個頂點的圖，建立一個V*V的布爾數(shù)組，如果頂點i到j之間有邊連接，則定義i行j列的元素值為true，否則為false，如果是帶有權值的圖，那么將true改成相應的權值，false改成一個不太可能出現(xiàn)的值比如Integer.MAX_VALUE。還可以專門用一個數(shù)組或者表，用來存放頂點信息，因為我們直接用0~N - 1的值代表了每個頂點，但這些數(shù)值具體指代了什么意思可以去頂點信息數(shù)組查找。不過鄰接矩陣表示對于頂點數(shù)目很多（比如上百萬）的圖，N*N個值的空間是不能滿足的。

如上，左邊的無向圖可以轉換成右邊的鄰接矩陣。頂點0~3的信息存在頂點信息數(shù)組里。由于這里用的是大話數(shù)據(jù)結構（C語言）中的圖，0其實就是false，1就是true。頂點v0和v1有邊相連，所以在矩陣中a[0][1]和a[1][0]的值為true，而v1和v3之間沒有邊相連所以a[1][3]和a[3][1]為false。仔細觀察可以發(fā)現(xiàn)主對角線的值全是0，這是因為我們討論的是簡單圖，暫時不考慮自環(huán)的情況。以主對角線為對稱軸，矩陣左下a[i][j]和對應右上的a[j][i]值是一樣的，這其實是一個對稱矩陣。通過鄰接矩陣，我們還可以獲得一些其他信息。

  • 某個頂點i的度其實就是矩陣中a[i]那行中true的個數(shù)。
  • 與頂點i相鄰的頂點就是矩陣中a[i]那行中所有值為true的列下標。

鄰接矩陣對于有向圖也適用，只是矩陣不再是對稱矩陣了。

如圖v0到v3有路徑，所以a[0][3]為true，但是v3到v0不存在路徑，所以a[3][0]為false。在有向圖中我們說到度，一般區(qū)分出度和入度。這些信息也可以從矩陣中看出。

  • 頂點i的出度是矩陣a[i]那行中值為true的個數(shù)。
  • 頂點i的入度是矩陣a[][i]那列中值為true的個數(shù)。

如果圖的邊是帶有權值的（加權圖），鄰接矩陣可以使用一個二維int數(shù)組，如果兩個頂點之間存在路徑就用該邊的權值代替原布爾數(shù)組中的true，如果兩個頂點間沒不存在路徑就用一個不大可能出現(xiàn)的值代替false，由于權值可能為負數(shù)，我們選用Integer.MAX_VALUE。

圖中的“無窮”符號，就是我們選用的Integer的最大值。主對角線依然全是0，因為某個頂點到自身并不需要花費什么代價（可以理解為權值為0）。

雖然鄰接矩陣在頂點數(shù)巨大的時候，所用空間令人發(fā)指，而且它還存了那么多沒用的值——兩個頂點不存在路徑也存入了false或者一個不太可能出現(xiàn)的大值。但是無向圖、有向圖、加權無向圖、加權有向圖它都能實現(xiàn)，所以還是有必要動手敲一敲。

package Chap7;

import java.util.ArrayList;
import java.util.List;

/**
 * 無向圖 -- 鄰接矩陣
 * @param <Item> 頂點類型
 */
public class AdjMatrixGraph<Item> {
    private int vertexNum;
    private int edgeNum;
    // 鄰接矩陣
    private boolean[][] adj;
    // 存放所有頂點信息
    private Item[] vertexInfo;

    // 初始化有V個頂點的圖，還未加邊
    public AdjMatrixGraph(Item[] vertexInfo) {
        this.vertexNum = vertexInfo.length;
        this.vertexInfo = vertexInfo;

        adj = new boolean[vertexNum][vertexNum];
    }

    public AdjMatrixGraph(Item[] vertexInfo, int[][] edges) {
        this(vertexInfo);
        for (int[] twoVertex : edges) {
            addEdge(twoVertex[0], twoVertex[1]);
        }
    }

    public AdjMatrixGraph(int vertexNum) {
        this.vertexNum = vertexNum;
        adj = new boolean[vertexNum][vertexNum];
    }

    public AdjMatrixGraph(int vertexNum,int[][] edges) {
        this(vertexNum);
        for (int[] twoVertex : edges) {
            addEdge(twoVertex[0], twoVertex[1]);
        }
    }

    public void addEdge(int i, int j) {
        // 對稱矩陣，所以a[i][j] = a[j][i]
        adj[i][j] = true;
        adj[j][i] = true;
        edgeNum++;
    }

    public int vertexNum() {
        return vertexNum;
    }

    public int edgenum() {
        return edgeNum;
    }

    public Item getVertexInfo(int i) {
        return vertexInfo[i];
    }
    // 求某頂點的所有鄰接頂點
    public List<Integer> adj(int i) {
        List<Integer> vertexAdj = new ArrayList<>();
        for (int j = 0; j < adj[i].length; j++) {
            if (adj[i][j]) {
                vertexAdj.add(j);
            }
        }
        return vertexAdj;
    }

    // 某頂點的度
    public int degree(int i) {
        int degree = 0;
        for (int j = 0; j < adj[i].length; j++) {
            if (adj[i][j]) {
               degree++;
            }
        }
        return degree;
    }
    // 求圖的最大度數(shù)
    public int maxDegree() {
        int max = 0;
        for (int i = 0; i < vertexNum; i++) {
            if (degree(i) > max) {
                max = degree(i);
            }
        }
        return max;
    }
    // 求圖的平均度數(shù)
    // 邊的條數(shù) = 頂點度之和的一半  因為一條邊對應兩個頂點，這兩個頂點的度數(shù)之和為2，所以邊的數(shù)量是度之和的一半這樣的關系
    // edgeNum = sum / 2, 則sum = 2 * edgeNum, 于是avgDegree = sum / vertexNum
    public double avgDegree() {
        return 2.0 * edgeNum / vertexNum;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(vertexNum).append("個頂點, ").append(edgeNum).append("條邊。\n");
        for (int i = 0; i < vertexNum; i++) {
            sb.append(i).append(": ").append(adj(i)).append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        String[] vertexInfo = {"v0", "v1", "v2", "v3", "v4"};
        int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                {1, 3}, {1, 4},
                {2, 4}};
        AdjMatrixGraph<String> graph = new AdjMatrixGraph<>(vertexInfo,edges);

        System.out.println("頂點3的度為" + graph.degree(3));
        System.out.println("頂點3的鄰接點為"+graph.adj(3));
        System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
        System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
        System.out.println("鄰接矩陣如下:\n" + graph);
    }
}

/* Outputs
頂點3的度為2
頂點3的鄰接點為[0, 1]
該圖的最大度數(shù)為3
該圖的平均度數(shù)為2.4
鄰接矩陣如下:
5個頂點, 6條邊。
0: [1, 2, 3]
1: [0, 3, 4]
2: [0, 4]
3: [0, 1]
4: [1, 2]

*/

我們的實現(xiàn)中有兩個構造器，其中一個接收一個參數(shù)，傳入頂點信息數(shù)組，以頂點信息個數(shù)作為圖的頂點數(shù)。另外一個還可以接收表示所有相鄰頂點的二維數(shù)組，比如edges[0] = {0, 1}表示頂點0和頂點1相鄰，由于addEdge方法中已經(jīng)考慮了對稱矩陣，所以這里傳參的時候就用不著傳入{0， 1}后再傳入{1, 0}了，只要保證前一個數(shù)比后一個數(shù)小就可以避免重復添加。

這里重點說一下求圖的平均度數(shù)的方法avgDegree，我們有一個結論：圖的邊的條數(shù) = 頂點度之和的一半，這是因為每一條邊對應著兩個頂點，而這兩個頂點對于這條邊，度之和為2。所以邊的條數(shù)是所有頂點度之和的一半，即edgeNum = sum / 2，則sum = 2 * edgeNum， 于是avgDegree = sum / vertexNum

鄰接表

鄰接數(shù)組的缺點是所用空間太多，而且存放的信息很多是多余——頂點沒有相鄰也非得用一個false值或者不太可能出現(xiàn)的大值去填補數(shù)組中的位置，為何不直接留下相鄰頂點就行了？比如上例中的a[0]，可以從矩陣中看出與頂點0相鄰的有頂點1、2、3

    0       1       2       3       4       5       
0   false   true    true    true    false   false

為什么不直接存儲為a[0] = [1, 2, 3]（就像上面打印的一樣），這不是直觀了很多嘛。由于每個頂點擁有的鄰接點數(shù)目不同，使用數(shù)組實現(xiàn)就浪費空間了。所以存放某個頂點所有鄰接點的容器，使用可變容量的表是個不錯的選擇，這里我就用鏈表了。回想樹的孩子表示法，和這是一個道理，只是孩子表示法中存放的是結點對象(Node)，這里存放的是用整數(shù)表示的頂點。鄰接表不像鄰接矩陣那樣容量固定，如果某幅圖要添加、刪除某個頂點或某條邊是相當方便的。所以在之后的實現(xiàn)中，如果沒有特殊需求，將會一直使用鄰接表。

package Chap6;

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

/**
 * 無向圖
 * @param <Item>
 */
public class UndiGraph<Item> {
    private int vertexNum;
    private int edgeNum;
    // 鄰接表
    private List<List<Integer>> adj;
    // 頂點信息
    private List<Item> vertexInfo;

    public UndiGraph(List<Item> vertexInfo) {
        this.vertexInfo = vertexInfo;
        this.vertexNum = vertexInfo.size();
        adj = new ArrayList<>();
        for (int i = 0; i < vertexNum; i++) {
            adj.add(new LinkedList<>());
        }
    }

    public UndiGraph(List<Item> vertexInfo, int[][] edges) {
        this(vertexInfo);
        for (int[] twoVertex : edges) {
            addEdge(twoVertex[0], twoVertex[1]);
        }
    }

    public int vertexNum() {
        return vertexNum;
    }

    public int edgeNum() {
        return edgeNum;
    }

    public void addEdge(int i, int j) {
        adj.get(i).add(j);
        adj.get(j).add(i);
        edgeNum++;
    }
    // 不需要set，所以不用返回List，返回可迭代對象就夠了
    public Iterable<Integer> adj(int i) {
        return adj.get(i);
    }

    public Item getVertexInfo(int i) {
        return vertexInfo.get(i);
    }

    public int degree(int i) {
        return adj.get(i).size();
    }

    public int maxDegree() {
        int max = 0;
        for (int i = 0;i < vertexNum;i++) {
            if (degree(i) > max) {
                max = degree(i);
            }
        }
        return max;
    }

    public double avgDegree() {
        return 2.0 * edgeNum / vertexNum;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(vertexNum).append("個頂點, ").append(edgeNum).append("條邊。\n");
        for (int i = 0; i < vertexNum; i++) {
            sb.append(i).append(": ").append(adj.get(i)).append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
        int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                {1, 3}, {1, 4},
                {2, 4}};

        UndiGraph<String> graph = new UndiGraph<>(vertexInfo, edges);
        
        System.out.println("頂點3的度為" + graph.degree(3));
        System.out.println("頂點3的鄰接點為"+graph.adj(3));
        System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
        System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
        System.out.println("鄰接表如下:\n" + graph);
    }

}

程序輸出和上面鄰接矩陣實現(xiàn)的輸出完全一樣。各個方法的實現(xiàn)其思想和鄰接矩陣實現(xiàn)類似，比較簡單就不解釋了。

順便把有向圖也用鄰接表實現(xiàn)了。

package Chap7;

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

/**
 * 無向圖
 *
 * @param <Item>
 */
public class DiGraph<Item> {
    private int vertexNum;
    private int edgeNum;
    // 鄰接表
    private List<List<Integer>> adj;
    // 頂點信息
    private List<Item> vertexInfo;

    public DiGraph(List<Item> vertexInfo) {
        this.vertexInfo = vertexInfo;
        this.vertexNum = vertexInfo.size();
        adj = new ArrayList<>();
        for (int i = 0; i < vertexNum; i++) {
            adj.add(new LinkedList<>());
        }
    }

    public DiGraph(List<Item> vertexInfo, int[][] edges) {
        this(vertexInfo);
        for (int[] twoVertex : edges) {
            addEdge(twoVertex[0], twoVertex[1]);
        }
    }

    public DiGraph(int vertexNum) {
        this.vertexNum = vertexNum;
        adj = new ArrayList<>();
        for (int i = 0; i < vertexNum; i++) {
            adj.add(new LinkedList<>());
        }
    }

    public DiGraph(int vertexNum, int[][] edges) {
        this(vertexNum);
        for (int[] twoVertex : edges) {
            addEdge(twoVertex[0], twoVertex[1]);
        }
    }

    public int vertexNum() {
        return vertexNum;
    }

    public int edgeNum() {
        return edgeNum;
    }

    public void addEdge(int i, int j) {
        adj.get(i).add(j);
        edgeNum++;
    }

    // 不需要set，所以不用返回List，返回可迭代對象就夠了
    public Iterable<Integer> adj(int i) {
        return adj.get(i);
    }

    public DiGraph<Item> reverse() {
        DiGraph<Item> R = new DiGraph<>(vertexNum);
        for (int v = 0; v < vertexNum; v++) {
            for (int w: adj(v)) {
                R.addEdge(w, v);
            }
        }
        return R;
    }

    public Item getVertexInfo(int i) {
        return vertexInfo.get(i);
    }

    public int degree(int i) {
        return adj.get(i).size();
    }

    public int maxDegree() {
        int max = 0;
        for (int i = 0; i < vertexNum; i++) {
            if (degree(i) > max) {
                max = degree(i);
            }
        }
        return max;
    }

    public double avgDegree() {
        return 2.0 * edgeNum / vertexNum;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(vertexNum).append("個頂點, ").append(edgeNum).append("條邊。\n");
        for (int i = 0; i < vertexNum; i++) {
            sb.append(i).append(": ").append(adj.get(i)).append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
        int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                {1, 3}, {1, 4},
                {2, 4}};

        DiGraph<String> graph = new DiGraph<>(vertexInfo, edges);

        System.out.println("頂點3的度為" + graph.degree(3));
        System.out.println("頂點3的鄰接點為" + graph.adj(3));
        System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
        System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
        System.out.println("鄰接表如下:\n" + graph);
    }

}

addEdge方法少了一行，有向圖嘛，邊也是有方向的，i -> j有邊不一定j -> i有邊。另外新增了一個反向圖的reverse方法，改變了所有邊的方向，并返回原圖的反向圖。代碼中主要做的是對每個頂點v，以及v的所有鄰接頂點w，本來是v -> w的方向，現(xiàn)在新圖中調用addEdge(w, v)，將方向變成w -> v，實現(xiàn)反向。

至于其他方法，和無向圖完全一樣。

邊的數(shù)組

這種方法實現(xiàn)起來很簡單，顧名思義它更關注邊，我們可以用一個Edge來抽象邊，它有兩個int成員表示該邊的兩個頂點，如果是加權圖，再多一個int型的weight成員就行了。將所有邊存放到一個列表List<Edge>中，就是我們所說的邊的數(shù)組了。

package Chap7;

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

public class EdgeGraph<Item> {

    public static class Edge {
        private int either;
        private int other;

        public int either() {
            return either;
        }

        public int other() {
            return other;
        }

        public Edge(int either, int other) {
            this.either = either;
            this.other = other;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "either=" + either +
                    ", other=" + other +
                    '}';
        }
    }

    private int vertexNum;
    private int edgeNum;
    private List<Item> vertexInfo;
    private List<Edge> edges;

    public EdgeGraph(List<Item> vertexInfo) {
        this.edges = new ArrayList<>();
        this.vertexInfo = vertexInfo;
        this.vertexNum = vertexInfo.size();
    }

    public EdgeGraph(List<Item> vertexInfo, int[][] edges) {
        this(vertexInfo);
        for (int[] twoVertex : edges) {
            addEdge(twoVertex[0], twoVertex[1]);
        }
    }

    public EdgeGraph(int vertexNum) {
        this.edges = new ArrayList<>();
        this.vertexNum = vertexNum;
    }

    public EdgeGraph(int vertexNum, int[][] edges) {
        this(vertexNum);
        for (int[] twoVertex : edges) {
            addEdge(twoVertex[0], twoVertex[1]);
        }
    }

    public void addEdge(int i, int j) {
        Edge edge = new Edge(i, j);
        this.edges.add(edge);
        edgeNum++;
    }

    public List<Integer> adj(int i) {
        List<Integer> adj = new ArrayList<>();

        for (Edge edge : edges) {
            if (edge.either == i) {
                adj.add(edge.other);
            } else if (edge.other == i) {
                adj.add(edge.either);
            }
        }
        return adj;
    }

    public int degree(int i) {
        return adj(i).size();
    }

    public int maxDegree() {
        int max = 0;
        for (int i = 0; i < vertexNum; i++) {
            if (degree(i) > max) {
                max = degree(i);
            }
        }
        return max;
    }

    public double avgDegree() {
        return 2.0 * edgeNum / vertexNum;
    }

    public Item getVertexInfo(int i) {
        return vertexInfo.get(i);
    }

    public int vertexNum() {
        return vertexNum;
    }

    public int edgeNum() {
        return edgeNum;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(vertexNum).append("個頂點, ").append(edgeNum).append("條邊。\n");
        for (int i = 0; i < vertexNum; i++) {
            sb.append(i).append(": ").append(adj(i)).append("\n");
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        List<String> vertexInfo = Arrays.asList("v0", "v1", "v2", "v3", "v4");
        int[][] edges = {{0, 1}, {0, 2}, {0, 3},
                {1, 3}, {1, 4},
                {2, 4}};
        EdgeGraph<String> graph = new EdgeGraph<>(vertexInfo, edges);
        System.out.println("頂點3的度為" + graph.degree(3));
        System.out.println("頂點3的鄰接點為" + graph.adj(3));
        System.out.println("該圖的最大度數(shù)為" + graph.maxDegree());
        System.out.println("該圖的平均度數(shù)為" + graph.avgDegree());
        System.out.println("鄰接表如下:\n" + graph);
    }
}

自然輸出和前面都一樣。

只說addEdge(int i, int j)方法和adj(int i)方法。前者給圖中兩個頂點添加一條邊，傳入兩個頂點，緊接著就new一個對應Edge，再將其存入邊的列表即可。后者獲取某個頂點所有鄰接點，遍歷邊的列表，因為不知道邊中哪個頂點和i相等，所以需要判斷一下，只要有一個頂點和i相等，就將另一個存入待返回的列表中。

現(xiàn)在也知道了該實現(xiàn)有個缺陷：要知道某個頂點的所有鄰接點，必須遍歷整個邊數(shù)組，效率不是很高。如果我們經(jīng)常進行對頂點的操作，可以說獲取某頂點所有鄰接點是非常頻繁的，邊的數(shù)組不太適合經(jīng)常對圖的頂點進行操作的場合，更適合經(jīng)常對邊進行依次操作的場合。

在后面加權圖的實現(xiàn)中，我們會用到邊的數(shù)組的思想，因為權值在邊上嘛，鄰接矩陣實現(xiàn)起倒是簡單，但是對于鄰接表來說，由上面可以知道它定義為List<List<Integer>>，內層列表存放的是頂點的所有鄰接點，那么權值存在哪里？這時候我們就需要一個Edge類了。差不多像下面這樣。

public class Edge {
    private int either;
    private int other;
    private int weight;
}

鄰接表隨之也變成了List<List<Edge>>。這里只是稍微提一下，以后學到加權圖的時候再具體來說。

by @sunhaiyu

2017.9.17

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

相關閱讀更多精彩內容

友情鏈接更多精彩內容