算法與數(shù)據(jù)結(jié)構(gòu)（八）圖 基礎(chǔ)篇

圖（Graph）是另一種非線性表數(shù)據(jù)結(jié)構(gòu)，和樹比起來，圖更加復(fù)雜。

我們首先了解一下圖的幾個(gè)關(guān)鍵概念：

• 頂點(diǎn) vertex：下圖中 A、B、C、D、E、F 就是頂點(diǎn)；

• 邊 edge：頂點(diǎn)之間的連線就是邊，邊可以是有向的，也可以是無向的；

• 我們把邊有方向的圖叫做“有向圖”；

• 沒有方向的圖就叫做“無向圖”；

• 在帶權(quán)圖中，每條邊有一個(gè)權(quán)重 weight；

• 度 degree：頂點(diǎn)的度是指與該頂點(diǎn)相關(guān)聯(lián)的邊的條數(shù)；

• 在有向圖中，我們把度分為入度和出度；

• 入度是指指向該頂點(diǎn)的邊的數(shù)量；

• 出度是指由該頂點(diǎn)指向其他頂點(diǎn)的邊的數(shù)量；

圖一般用在描述事物之間的關(guān)系，比如社交網(wǎng)絡(luò)中的用戶之間的關(guān)系、城市之間的交通等等。有向圖可以表示社交網(wǎng)絡(luò)中用戶之間的關(guān)注關(guān)系，無向圖可以表示用戶之間的好友關(guān)系，帶權(quán)圖則可以額外表示用戶之間的親密度。

圖的存儲

鄰接表

圖的存儲其中一種實(shí)現(xiàn)方式是鄰接表，對于下圖來說，鄰接表的存儲方式如圖右邊所示。

其 Java 代碼表示如下：

static class Node {
    public int value;
    public ArrayList<Node> nexts;

    public Node(int value) {
        this.value = value;
        nexts = new ArrayList<>();
    }
}

鄰接矩陣

圖的另一種實(shí)現(xiàn)方式鄰接矩陣，鄰接矩陣的底層依賴一個(gè)二維數(shù)組。對于下圖來說，鄰接矩陣的存儲方式如圖下方所示。可以看到鄰接矩陣比較浪費(fèi)空間。

無向圖的鄰接矩陣 Java 代碼表示如下：

public class Graph {
    private int v; // 頂點(diǎn)的個(gè)數(shù)
    private int[][] adj; // 鄰接表

    public Graph(int v) {
        this.v = v;
        this.adj = new int[v][v];
        for (int i = 0; i < v; ++i) {
            adj[i][i] = 0;
        }
    }

    public void addEdge(int s, int t) { // s 先于 t，邊 s->t
        adj[s][t] = 1;
    }
}

圖的搜索

廣度優(yōu)先搜索

廣度優(yōu)先搜索（Breadth-First-Search，BFS）首先將根節(jié)點(diǎn)放入隊(duì)列中，然后從其子節(jié)點(diǎn)開始，依次將子節(jié)點(diǎn)放入隊(duì)列的末尾。它在遍歷同一層上的所有節(jié)點(diǎn)之前，不會遍歷下一層的節(jié)點(diǎn)。

廣度優(yōu)先算法可以解決兩類問題：

1. 從節(jié)點(diǎn) A 出發(fā)，有沒有前往節(jié)點(diǎn) B 的路徑；

2. 從節(jié)點(diǎn) A 出發(fā)，前往節(jié)點(diǎn) B 的最短路徑是什么。

廣度優(yōu)先搜索的時(shí)間復(fù)雜度是 O(V+E)，其中 V 表示頂點(diǎn)的數(shù)量，E 表示邊的數(shù)量。以下是圖廣度優(yōu)先搜索的 Java 代碼表示，在遍歷的過程中，需要借助隊(duì)列這一數(shù)據(jù)結(jié)構(gòu)：

public static void bfs(Node node) {
    if (node == null) return;
    Queue<Node> queue = new LinkedList<>();
    Set<Node> visited = new HashSet<>();
    queue.add(node);
    visited.add(node);
    while (!queue.isEmpty()) {
        Node cur = queue.poll();
        System.out.println(cur.value);
        for (Node next : cur.nexts) {
            if (!visited.contains(next)) {
                queue.add(next);
                visited.add(next);
            }
        }
    }
}

深度優(yōu)先搜索

深度優(yōu)先搜索（Depth-First-Search，DFS）使用的是回溯思想，會優(yōu)先遍歷當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)，而不是鄰居節(jié)點(diǎn)。

深度優(yōu)先搜索的時(shí)間復(fù)雜度是 O(V+E)，其中 V 表示頂點(diǎn)的數(shù)量，E 表示邊的數(shù)量。以下是圖深度優(yōu)先搜索的遞歸 Java 代碼表示。在遍歷的過程中，如果不采用遞歸，則需要棧這一數(shù)據(jù)結(jié)構(gòu)來輔助遍歷：

// 遞歸實(shí)現(xiàn)
public static void dfs(Node s) {
    Set<Node> visited = new HashSet<>();
    recurDfs(s, visited);
}

private static void recurDfs(Node node, Set<Node> visited) {
    visited.add(node);
    System.out.println(node.value);
    for (Node q : node.nexts) {
        if (!visited.contains(q)) {
            recurDfs(q, visited);
        }
    }
}

// 非遞歸實(shí)現(xiàn)
public static void dfsWithStack(Node s) {
    Stack<Node> stack = new Stack<>();
    Set<Node> visited = new HashSet<>();

    stack.add(s);
    visited.add(s);
    while (!stack.isEmpty()) {
        Node cur = stack.pop();
        System.out.println(cur.value);
        for (Node item : cur.nexts) {
            if (!visited.contains(item)) {
                stack.add(item);
                visited.add(item);
            }
        }
    }
}

廣度優(yōu)先搜索和深度優(yōu)先搜索簡單粗暴，沒有做什么優(yōu)化，僅適用于簡單的圖搜索問題。如果圖比較大，搜索的終點(diǎn)離起點(diǎn)比較遠(yuǎn)，那這兩種搜索算法就會消耗很長的時(shí)間。