# Graph

## 概念

**图**（Graph）是一种非线性表结构。图中的元素叫做**顶点**（vertex），图中的顶点可以与任意其它顶点建立连接，这种连接叫做**边**（edge），与顶点相连接的边数叫做**度**（degree）。

边有方向的图叫做**有向图**，比如微博的用户关注与粉丝的关系，有向图中的度分为**出度**（Out-degree）和**入度**（In-degree）。入度表示指向这个顶点的边数，即粉丝数；出度表示这个顶点指向多少个其它顶点，即关注数。边没有方向的叫做**无向图**，比如微信好友关系。

边有权重的图叫做**带权图**（weighted graph），比如 qq 好友的亲密度。

所有的顶点都是连通的图叫做**连通图**。

## 存储

### 邻接矩阵

邻接矩阵（Adjacency Matrix）底层依赖于一个二维数组。如下图：

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-M00ZuEDTg88fWcfDvkH%2F-M00dF6nA2vqz96AvP2T%2Fimage.png?alt=media\&token=0e16b98f-0bd6-42e5-9dd1-5c0f2d5c467a)

**缺点**：浪费存储空间。若是无向图，就白白浪费一半。若是稀疏图，则浪费非常严重，比如微信几亿用户。

**优点**：获取顶点关系时非常高效；方便计算，很多问题可以转换为矩阵计算。

### 邻接表

邻接表（Adjacency List）底层依赖于一维数组 + 列表。每个顶点对应一个列表。如下图：

![](https://3232244687-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LYZow-MmROshIrkwdtE%2F-M00ZuEDTg88fWcfDvkH%2F-M00eryJhxNRVGLjdAGd%2Fimage.png?alt=media\&token=053daaf9-2b5c-4986-9c16-8bf999c4b433)

这就是时间换空间的思想。尽管节约了很多空间，但是使用起来比较耗时。

```java
// 无向图的实现
public final class Graph {
    private final int v;
    private final List<Integer>[] adj;

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

    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }
}
```

**优化**：可以将列表换成其它数据结构，比如红黑树、跳表、散列表、有序动态数组（可用二分查找）等。

{% hint style="info" %}
对于有向图来说，列表存储的是顶点指向的顶点，所以很容易查找用户关注了哪些用户。但是若要查找用户的粉丝列表，就很困难。所以需要一个**逆邻接表**，顶点存储的是指向它的顶点。
{% endhint %}

## BFS

广度优先搜索（Breath-First-Search）即先查找最近的，然后是次近的。

```java
/**
* bfs 搜索到的路径就是最短路径
*/
public void bfs(int s, int t) {
    int[] prev = new int[v];
    Arrays.fill(prev, -1);
    
    if (s == t) {
        print(prev, t);
    }
    
    boolean[] visited = new boolean[v];
    Arrays.fill(visited, false);
    visited[s] = true;
    
    Queue<Integer> queue = new LinkedList<>();
    queue.add(s);
    
    while (queue.size() > 0) {
        Integer p = queue.poll();
        for (int i : adj[p]) {
            if (!visited[i]) {
                prev[i] = p;
                if (i == t) {
                    print(prev, t);
                    return;
                }
                visited[i] = true;
                queue.add(i);
            }
        }
    }
}
```

时间复杂度 O(E)，空间复杂度 O(V)，E 表示边数，V 表示顶点数。

### 例题

* [LeetCode 102：二叉树按层输出。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/tree/LT102.java)

## DFS

深度优先搜索（Depth-First-Search）采用的是回溯思想，非常适合递归实现。

```java
/**
* dfs 搜索到的路径不一定是最短路径
*/
public void dfs(int s, int t) {
    final AtomicReference<Boolean> found = new AtomicReference<>(false);
    
    boolean[] visited = new boolean[v];
    Arrays.fill(visited, false);
    
    int[] prev = new int[v];
    Arrays.fill(prev, -1);
    
    recurDfs(found, visited, prev, s, t);
    print(prev, t);
}

private void recurDfs(AtomicReference<Boolean> found, boolean[] visited, int[] prev, int s, int t) {
    if (visited[s] || found.get()) {
        return;
    }
    if (s == t) {
        found.set(true);
        return;
    }
    visited[s] = true;
    for (Integer i : adj[s]) {
        prev[i] = s;
        recurDfs(found, visited, prev, i, t);
    }
}
```

时间复杂度 O(E)，空间复杂度 O(V)，E 表示边数，V 表示顶点数。

{% hint style="info" %}
DFS 和 BFS 是最简单的两种搜索方法，简单粗暴，没有什么优化，也叫做暴力搜索算法。**适合于状态空间不大的图的搜索。**
{% endhint %}

### 例题

* [LeetCode 104：二叉树叶子节点的最小深度。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/tree/LT104.java)
* [LeetCode 111：二叉树叶子节点的最大深度。](https://github.com/StoneYunZhao/algorithm/blob/master/src/main/java/com/zhaoyun/leetcode/tree/LT111.java)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://yunzhao.gitbook.io/notes/computer-science/algorithm/graph.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.