Java實(shí)現(xiàn)無向圖的示例詳解

更新時(shí)間：2022年04月06日 08:14:50 作者：之一Yo

邊沒有方向的圖稱為無向圖，直觀來說，若一個(gè)圖中每條邊都是無方向的，則稱為無向圖。本文將通過示例詳細(xì)講解Java如何實(shí)現(xiàn)無向圖，需要的可以參考一下

基本概念

圖的定義

一個(gè)圖是由點(diǎn)集V={v_i} 和 VV 中元素的無序?qū)Φ囊粋€(gè)集合E={e_k} 所構(gòu)成的二元組，記為G=(V,E)，V中的元素v_i叫做頂點(diǎn)，E中的元素 e_k叫做邊。

對(duì)于V中的兩個(gè)點(diǎn) u,v，如果邊(u,v) 屬于E，則稱 u,v兩點(diǎn)相鄰，u,v稱為邊(u,v)的端點(diǎn)。

我們可以用m(G)=|E| 表示圖G中的邊數(shù)，用n(G)=|V|表示圖G中的頂點(diǎn)個(gè)數(shù)。

無向圖的定義

對(duì)于E中的任意一條邊(vi,vj)，如果邊(vi,vj) 端點(diǎn)無序，則它是無向邊，此時(shí)圖G稱為無向圖。無向圖是最簡(jiǎn)單的圖模型，下圖顯示了同一幅無向圖，頂點(diǎn)使用圓圈表示，邊則是頂點(diǎn)之間的連線，沒有箭頭（圖片來自于《算法第四版》）：

無向圖的 API

對(duì)于一幅無向圖，我們關(guān)心圖的頂點(diǎn)數(shù)、邊數(shù)、每個(gè)頂點(diǎn)的相鄰頂點(diǎn)和邊的添加操作，所以接口如下所示：

package com.zhiyiyo.graph;

/**
 * 無向圖
 */
public interface Graph {
    /**
     * 返回圖中的頂點(diǎn)數(shù)
     */
    int V();

    /**
     * 返回圖中的邊數(shù)
     */
    int E();

    /**
     * 向圖中添加一條邊
     * @param v 頂點(diǎn) v
     * @param w 頂點(diǎn) w
     */
    void addEdge(int v, int w);

    /**
     * 返回所有相鄰頂點(diǎn)
     * @param v 頂點(diǎn) v
     * @return 所有相鄰頂點(diǎn)
     */
    Iterable<Integer> adj(int v);
}

無向圖的實(shí)現(xiàn)方式

鄰接矩陣

用矩陣表示圖對(duì)研究圖的性質(zhì)及應(yīng)用常常是比較方便的，對(duì)于各種圖有各種矩陣表示方式，比如權(quán)矩陣和鄰接矩陣，這里我們只關(guān)注鄰接矩陣。它的定義為：

對(duì)于圖G=(V,E)，|V|=n，構(gòu)造一個(gè)矩陣 A=(a_ij)_n×n，其中：

則稱矩陣A為圖G的鄰接矩陣。

由定義可知，我們可以使用一個(gè)二維的布爾數(shù)組 A 來實(shí)現(xiàn)鄰接矩陣，當(dāng) A[i][j] = true 時(shí)說明頂點(diǎn) i 和 j 相鄰。

對(duì)于 n個(gè)頂點(diǎn)的圖 G，鄰接矩陣需要消耗的空間為 n²個(gè)布爾值的大小，對(duì)于稀疏圖來說會(huì)造成很大的浪費(fèi)，當(dāng)頂點(diǎn)數(shù)很大時(shí)所消耗的空間會(huì)是個(gè)天文數(shù)字。同時(shí)當(dāng)圖比較特殊，存在自環(huán)以及平行邊時(shí)，鄰接矩陣的表示方式是無能為力的?！端惴ā分薪o出了存在這兩種情況的圖：

邊的數(shù)組

對(duì)于無向圖，我們可以實(shí)現(xiàn)一個(gè)類 Edge，里面只用兩個(gè)實(shí)例變量用來存儲(chǔ)兩個(gè)頂點(diǎn) u和 v，接著在一個(gè)數(shù)組里面保存所有 Edge 即可。這樣做有一個(gè)很大的問題，就是在獲取頂點(diǎn) v的所有相鄰頂點(diǎn)時(shí)必須遍歷整個(gè)數(shù)組才能得到，時(shí)間復(fù)雜度是O(|E|)，由于獲取相鄰頂點(diǎn)是很常用的操作，所以這種表示方式也不太行。

鄰接表數(shù)組

如果我們把頂點(diǎn)表示為一個(gè)整數(shù)，取值范圍為0∼|V|−1，那么就可以用一個(gè)長(zhǎng)度為|V| 的數(shù)組的索引表示每一個(gè)頂點(diǎn)，然后將每一個(gè)數(shù)組元素設(shè)置為一個(gè)鏈表，上面掛載著索引所代表的的頂點(diǎn)相鄰的其他頂點(diǎn)。圖一所示的無向圖可以用下圖所示的鄰接表數(shù)組表示出來：

使用鄰接表實(shí)現(xiàn)無向圖的代碼如下所示，由于鄰接表數(shù)組中的每個(gè)鏈表都會(huì)保存與頂點(diǎn)相鄰的頂點(diǎn)，所以將邊添加到圖中時(shí)需要對(duì)數(shù)組中的兩個(gè)鏈表進(jìn)行添加節(jié)點(diǎn)的操作：

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;

/**
 * 使用鄰接表實(shí)現(xiàn)的無向圖
 */
public class LinkGraph implements Graph {
    private final int V;
    private int E;
    private LinkStack<Integer>[] adj;

    public LinkGraph(int V) {
        this.V = V;
        adj = (LinkStack<Integer>[]) new LinkStack[V];
        for (int i = 0; i < V; i++) {
            adj[i] = new LinkStack<>();
        }
    }

    @Override
    public int V() {
        return V;
    }

    @Override
    public int E() {
        return E;
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].push(w);
        adj[w].push(v);
        E++;
    }

    @Override
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
}

這里用到的棧代碼如下所示，棧的實(shí)現(xiàn)不是這篇博客的重點(diǎn)，所以這里不做過多解釋：

package com.zhiyiyo.collection.stack;

import java.util.EmptyStackException;
import java.util.Iterator;

/**
 * 使用鏈表實(shí)現(xiàn)的堆棧
 */
public class LinkStack<T> {
    private int N;
    private Node first;

    public void push(T item) {
        first = new Node(item, first);
        N++;
    }

    public T pop() throws EmptyStackException {
        if (N == 0) {
            throw new EmptyStackException();
        }

        T item = first.item;
        first = first.next;
        N--;
        return item;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    public Iterator<T> iterator() {
        return new ReverseIterator();
    }

    private class Node {
        T item;
        Node next;

        public Node() {
        }

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }


    private class ReverseIterator implements Iterator<T> {
        private Node node = first;

        @Override
        public boolean hasNext() {
            return node != null;
        }

        @Override
        public T next() {
            T item = node.item;
            node = node.next;
            return item;
        }

        @Override
        public void remove() {
        }
    }
}

無向圖的遍歷

給定下面一幅圖，現(xiàn)在要求找到每個(gè)頂點(diǎn)到頂點(diǎn) 0 的路徑，該如何實(shí)現(xiàn)？或者簡(jiǎn)單點(diǎn)，給定頂點(diǎn) 0 和 4，要求判斷從頂點(diǎn) 0 開始走，能否到達(dá)頂點(diǎn) 4，該如何實(shí)現(xiàn)？這就要用到兩種圖的遍歷方式：深度優(yōu)先搜索和廣度優(yōu)先搜索。

在介紹這兩種遍歷方式之前，先給出解決上述問題需要實(shí)現(xiàn)的 API：

package com.zhiyiyo.graph;

public interface Search {
    /**
     * 起點(diǎn) s 和 頂點(diǎn) v 之間是否連通
     * @param v 頂點(diǎn) v
     * @return 是否連通
     */
    boolean connected(int v);

    /**
     * 返回與頂點(diǎn) s 相連通的頂點(diǎn)個(gè)數(shù)（包括 s）
     */
    int count();

    /**
     * 是否存在從起點(diǎn) s 到頂點(diǎn) v 的路徑
     * @param v 頂點(diǎn) v
     * @return 是否存在路徑
     */
    boolean hasPathTo(int v);

    /**
     * 從起點(diǎn) s 到頂點(diǎn) v 的路徑，不存在則返回 null
     * @param v 頂點(diǎn) v
     * @return 路徑
     */
    Iterable<Integer> pathTo(int v);
}

深度優(yōu)先搜索

深度優(yōu)先搜索的思想類似樹的先序遍歷。我們從頂點(diǎn) 0 開始，將它的相鄰頂點(diǎn) 2、1、5 加到棧中。接著彈出棧頂?shù)捻旤c(diǎn) 2，將它相鄰的頂點(diǎn) 0、1、3、4 添加到棧中，但是寫到這你就會(huì)發(fā)現(xiàn)一個(gè)問題：頂點(diǎn) 0 和 1明明已經(jīng)在棧中了，如果還把他們加到棧中，那這個(gè)棧豈不是永遠(yuǎn)不會(huì)變回空。所以還需要維護(hù)一個(gè)數(shù)組 boolean[] marked，當(dāng)我們將一個(gè)頂點(diǎn) i 添加到棧中時(shí)，就將 marked[i] 置為 true，這樣下次要想將頂點(diǎn) i 加入棧中時(shí)，就得先檢查一個(gè) marked[i] 是否為 true，如果為 true 就不用再添加了。重復(fù)棧頂節(jié)點(diǎn)的彈出和節(jié)點(diǎn)相鄰節(jié)點(diǎn)的入棧操作，直到棧為空，我們就完成了頂點(diǎn) 0 可達(dá)的所有頂點(diǎn)的遍歷。

為了記錄每個(gè)頂點(diǎn)到頂點(diǎn) 0 的路徑，我們還需要一個(gè)數(shù)組 int[] edgeTo。每當(dāng)我們?cè)L問到頂點(diǎn) u 并將其一個(gè)相鄰頂點(diǎn) i 壓入棧中時(shí)，就將 edgeTo[i] 設(shè)置為 u，說明要想從頂點(diǎn)i 到達(dá)頂點(diǎn) 0，需要先回退頂點(diǎn) u，接著再?gòu)捻旤c(diǎn) edgeTo[u] 處獲取下一步要回退的頂點(diǎn)直至找到頂點(diǎn) 0。

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.stack.LinkStack;
import com.zhiyiyo.collection.stack.Stack;


public class DepthFirstSearch implements Search {
    private boolean[] marked;
    private int[] edgeTo;
    private Graph graph;
    private int s;
    private int N;

    public DepthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        marked = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        dfs();
    }

    /**
     * 遞歸實(shí)現(xiàn)的深度優(yōu)先搜索
     *
     * @param v 頂點(diǎn) v
     */
    private void dfs(int v) {
        marked[v] = true;
        N++;
        for (int i : graph.adj(v)) {
            if (!marked[i]) {
                edgeTo[i] = v;
                dfs(i);
            }
        }
    }

    /**
     * 堆棧實(shí)現(xiàn)的深度優(yōu)先搜索
     */
    private void dfs() {
        Stack<Integer> vertexes = new LinkStack<>();
        vertexes.push(s);
        marked[s] = true;

        while (!vertexes.isEmpty()) {
            Integer v = vertexes.pop();
            N++;

            // 將所有相鄰頂點(diǎn)加到堆棧中
            for (Integer i : graph.adj(v)) {
                if (!marked[i]) {
                    edgeTo[i] = v;
                    marked[i] = true;
                    vertexes.push(i);
                }
            }
        }
    }

    @Override
    public boolean connected(int v) {
        return marked[v];
    }

    @Override
    public int count() {
        return N;
    }

    @Override
    public boolean hasPathTo(int v) {
        return connected(v);
    }

    @Override
    public Iterable<Integer> pathTo(int v) {
        if (!hasPathTo(v)) return null;
        Stack<Integer> path = new LinkStack<>();

        int vertex = v;
        while (vertex != s) {
            path.push(vertex);
            vertex = edgeTo[vertex];
        }

        path.push(s);
        return path;
    }
}

廣度優(yōu)先搜索

廣度優(yōu)先搜索的思想類似樹的層序遍歷。與深度優(yōu)先搜索不同，從頂點(diǎn) 0 出發(fā)，廣度優(yōu)先搜索會(huì)先處理完所有與頂點(diǎn) 0 相鄰的頂點(diǎn) 2、1、5 后，才會(huì)接著處理頂點(diǎn) 2、1、5 的相鄰頂點(diǎn)。這個(gè)搜索過程就是一圈一圈往外擴(kuò)展、越走越遠(yuǎn)的過程，所以可以用來獲取頂點(diǎn) 0 到其他節(jié)點(diǎn)的最短路徑。只要將深度優(yōu)先搜索中的堆換成隊(duì)列，就能實(shí)現(xiàn)廣度優(yōu)先搜索：

package com.zhiyiyo.graph;

import com.zhiyiyo.collection.queue.LinkQueue;

public class BreadthFirstSearch implements Search {
    private boolean[] marked;
    private int[] edgeTo;
    private Graph graph;
    private int s;
    private int N;

    public BreadthFirstSearch(Graph graph, int s) {
        this.graph = graph;
        this.s = s;
        marked = new boolean[graph.V()];
        edgeTo = new int[graph.V()];
        bfs();
    }

    private void bfs() {
        LinkQueue<Integer> queue = new LinkQueue<>();
        marked[s] = true;
        queue.enqueue(s);

        while (!queue.isEmpty()) {
            int v = queue.dequeue();
            N++;

            for (Integer i : graph.adj(v)) {
                if (!marked[i]) {
                    edgeTo[i] = v;
                    marked[i] = true;
                    queue.enqueue(i);
                }
            }
        }
    }
}

隊(duì)列的實(shí)現(xiàn)代碼如下：

package com.zhiyiyo.collection.queue;


import java.util.EmptyStackException;


public class LinkQueue<T> {
    private int N;
    private Node first;
    private Node last;

    public void enqueue(T item) {
        Node node = new Node(item, null);
        if (++N == 1) {
            first = node;
        } else {
            last.next = node;
        }
        last = node;
    }

    public T dequeue() throws EmptyStackException {
        if (N == 0) {
            throw new EmptyStackException();
        }

        T item = first.item;
        first = first.next;
        if (--N == 0) {
            last = null;
        }
        return item;
    }

    public int size() {
        return N;
    }

    public boolean isEmpty() {
        return N == 0;
    }

    private class Node {
        T item;
        Node next;

        public Node() {
        }

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }
}