图

邻接矩阵：matrix[i][j] 表示点 i 到 j 的权重。如果是无权重的图，则 matrix[i][j] 保存布尔值代表有没有边。适合存储稠密矩阵。
邻接表：h[i] 中保存一个链表，链表元素是点 i 直接连接的点，类似HashMap的拉链法。链表节点的顺序无所谓。每个链表插入一个节点采用头插法。

数组模拟单链表

链表除了用LinkedList以外，也能用数组模拟，效率更高。用于存储图的邻接表。
搜索与图论 - 图1 e[i]: i 号节点的值。ne[i]: i 号节点的next节点号（指针），ne[tail] = -1。

插曲：静态变量、静态代码块、成员变量和构造函数在Java中的初始化顺序

下面展示了模拟单链表的所有操作，在邻接表中只需要使用addToHead()方法就足够。

import java.io.*;
public class Main {
    private static final int N = 100010;
    private static int head;
    private static int[] e = new int[N];
    private static int[] ne = new int[N];
    private static int idx; // 记录数组e已经使用到的下标位置
    private static void init() {
        head = -1; // 头节点为空节点
        idx = 0;
    }
    private static void addToHead(int val) {
        e[idx] = val;
        ne[idx] = head;
        head = idx ++ ;
    }
    /**
     * @param val 新节点e[idx]的值
     * @param k 插入到k号节点的后面
     */
    private static void add(int k, int val) {
        if (k == -1) {
            addToHead(val);
            return;
        }
        e[idx] = val;
        ne[idx] = ne[k];
        ne[k] = idx ++ ;
    }
    /**
     * @param k 删除k号节点的后一个节点
     */
    private static void remove(int k) {
        // 删除头节点
        if (k == -1) {
            head = ne[head];
            return;
        }
        ne[k] = ne[ne[k]]; // 不用考虑内存释放，效率优先
    }
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        // 读入操作次数m
        int m = Integer.parseInt(reader.readLine());
        // 初始化
        init();
        while (m -- > 0) {
            String[] input = reader.readLine().split(" ");
            if (input[0].equals("H")) {
                addToHead(Integer.parseInt(input[1]));
            }
            else if (input[0].equals("D")) {
                remove(Integer.parseInt(input[1]) - 1);
            }
            else if (input[0].equals("I")) {
                add(Integer.parseInt(input[1]) - 1, Integer.parseInt(input[2]));
            }
        }
        for (int i = head; i != -1; i = ne[i]) System.out.print(e[i] + " ");
    }
}

数组模拟单链表的操作是为用数组模拟邻接表做铺垫，以下为邻接表的结构，数组中每个下标存放了对应编号的节点邻接的节点编号。

由于是无向图Undirected Graph，链表的顺序是任意的。

模板

邻接表的表示

// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;
// 添加一条边a--b 头插法
void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
// 初始化
idx = 0;
memset(h, -1, sizeof h);

图DFS

int dfs(int u)
{
    st[u] = true; // st[u] 表示点u已经被遍历过
    for (int i = h[u]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j]) dfs(j);
    }
}

DFS模板题：树的重心

/*
https://www.acwing.com/problem/content/848/
给定一颗树，树中包含 n 个结点（编号 1∼n）和 n−1 条无向边。
请你找到树的重心，并输出将重心删除后，剩余各个连通块中点数的最大值。
重心定义：重心是指树中的一个结点，如果将这个点删除后，剩余各个连通块中点数的最大值最小，那么这个节点被称为树的重心。
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class Main {
    private static int N = 100010;
    // Represent Adjacency-lists
    private static int[] head = new int[N];
    private static int[] e = new int[N * 2]; // a->b b->a, so we need 2N space.
    private static int[] ne = new int[N * 2]; // Next pointer
    private static int index = 0;
    private static boolean[] visited = new boolean[N];
    private static int vertexNum = 0;
    private static int result = N;
    /**
     * Vertex b adjacent to vertex a.
     */
    private static void addEage(int a, int b) {
        // Insert vertex b before the head[a](logically), and reset head[a] as current index.
        e[index] = b;
        ne[index] = head[a];
        head[a] = index ++ ;
    }
    /**
     * @param n Traverse from vertex n
     * @return Number of vertices in sub-graph n
     */
    private static int dfs(int n) {
        visited[n] = true;
        int sum = 1, maxSubGraphSize = 0;
        // Traverse the vertices adjacent to n
        for (int i = head[n]; i != -1; i = ne[i]) {
            int vertex = e[i];
            if (!visited[vertex]) {
                int subGraphSize = dfs(vertex);
                sum += subGraphSize;
                // Find the largest subgraph.
                maxSubGraphSize = Math.max(maxSubGraphSize, subGraphSize);
                // maxSubGraphSize = Math.max(maxSubGraphSize, vertexNum - sum);
            }
        }
        maxSubGraphSize = Math.max(maxSubGraphSize, vertexNum - sum);
        result = Math.min(result, maxSubGraphSize);
        return sum;
    }
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        vertexNum = Integer.parseInt(reader.readLine());
        // -1 refers to null. Head nodes need to be set null.
        Arrays.fill(head, 1, vertexNum + 1, -1);
        // edge number = vertex number - 1
        for (int i = 0; i < vertexNum - 1; ++ i) {
            String[] vertices = reader.readLine().split(" ");
            int a = Integer.parseInt(vertices[0]), b = Integer.parseInt(vertices[1]);
            // Undirected Graph->vertices are connected in two directions.
            addEage(a, b);
            addEage(b, a);
        }
        dfs(1);
        System.out.println(result);
    }
}

由于是无向图，在添加邻接表元素的时候，两个方向都要添加。
dfs遍历时，需要每次设置该点已经访问过，然后深度搜索从该点派生的（链表中的），且没有被访问过的顶点。

图BFS

queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示点j已经被遍历过
            q.push(j);
        }
    }
}

图BFS模板题：图中点的层次

package graphs;
/*
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环。
所有边的长度都是 1，点的编号为 1∼n。
请你求出 1 号点到 n 号点的最短距离，如果从 1 号点无法走到 n 号点，输出 −1。
 */

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class AcWing847 {

    private static final int N = 100010;
    private static int[] head = new int[N];
    private static int[] e = new int[N];
    private static int[] ne = new int[N];
    private static int index = 0;
    private static int[] distance = new int[N];
    private static Deque<Integer> queue = new LinkedList<>();
    private static int n = 0;

    private static void addEdge(int a, int b) {
        e[index] = b;
        ne[index] = head[a];
        head[a] = index ++ ;
    }

    private static int bfs() {
        // Start from vertex 1.
        distance[1] = 0;
        queue.offerLast(1);
        while (!queue.isEmpty()) {
            int vertex = queue.pollFirst();
            // Where does this vertex can reach.
            for (int i = head[vertex]; i != -1; i = ne[i]) {
                int v = e[i];
                if (distance[v] == -1) {
                    distance[v] = distance[vertex] + 1;
                    queue.offerLast(v);
                }
            }
        }
        return distance[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] params = reader.readLine().split(" ");
        n = Integer.parseInt(params[0]);
        Arrays.fill(distance, 1, n + 1, -1);
        Arrays.fill(head, 1, n + 1, -1);
        int m = Integer.parseInt(params[1]);
        for (int i = 0; i < m; ++ i) {
            String[] indices = reader.readLine().split(" ");
            int a = Integer.parseInt(indices[0]);
            int b = Integer.parseInt(indices[1]);
            addEdge(a, b);
        }
        System.out.println(bfs());
    }
}

有向图的拓扑序列

拓扑序列：图中的每一条有向边u->v，都有u在v之前出现，则称该序列为图的拓扑序列。
搜索与图论 - 图4
有向无环图一定存在拓扑序列。有向无环图 = 拓扑图。

使用BFS获得有向图的拓扑序列

有向无环图的起始点的入度为0，所以从入度为0的点开始进行宽搜（将入度为0的点加入队列）。
当队列不为空，从队列中取出一个顶点，根据邻接表找到其派生出的顶点，将这些顶点的入度-1（断开连接），当该点入度=0，则加入队列。
1. 当入度为0，说明它已经没有任何前置顶点，能够被合法的加入拓扑序列中。
2. 若这是合法的有向无环图，一定满足所有的顶点都被加入过队列，即最终last = n - 1。
3. 由于采用数组模拟队列的方式，模拟列表的数组中保存的元素次序即为所求的拓扑序列。 ```java package graphs;

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader;

public class AcWing848 {

private static int vertexNum = 0;
private static final int N = 100010;
private static int[] head = new int[N];
private static int[] e = new int[N];
private static int[] ne = new int[N];
private static int index = 0;
private static int[] indegree = new int[N];
private static int[] queue = new int[N];

public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String[] params = reader.readLine().split(" ");
    vertexNum = Integer.parseInt(params[0]);
    for (int i = 1; i <= vertexNum; ++ i) head[i] = -1;
    int lineNum = Integer.parseInt(params[1]);
    for (int i = 0; i < lineNum; ++ i) {
        String[] vertices = reader.readLine().split(" ");
        int a = Integer.parseInt(vertices[0]), b = Integer.parseInt(vertices[1]);
        addEdge(a, b);
        indegree[b] ++ ;
    }
    if (topSort()) {
        for (int i = 0; i < vertexNum; ++ i) System.out.print(queue[i] + " ");
    }
    else System.out.println(-1);
}

private static void addEdge(int a, int b) {
    e[index] = b; ne[index] = head[a]; head[a] = index ++ ;
}

private static boolean topSort() {
    int first = 0, last = -1;
    // 1. Add verdices with indegree=0 to queue
    for (int i = 1; i <= vertexNum; ++ i) {
        if (indegree[i] == 0) queue[ ++ last] = i;
    }
    // 2. BFS
    while (first <= last) {
        // queue.pollFirst()
        int vertex = queue[first ++ ];
        for (int i = head[vertex]; i != -1; i = ne[i]) {
            int v = e[i];
            // Remove the link between v and vertex, indegree[v] - 1
            if ( -- indegree[v]== 0) queue[ ++ last] = v;
        }
    }
    // 3. Top sort is legal = All vertices have been added to queue
    return last == vertexNum - 1;
}

}

<a name="dxy5u"></a>
### BFS：八数码（数字滑块拼图）

- 将3x3棋盘状态用字符串表示，每个状态作为BFS的搜索节点。
```java
package graphs;
import java.io.*;
import java.util.*;

public class AcWing845 {
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] input = reader.readLine().split(" ");
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < input.length; ++ i) builder.append(input[i]);
        // initial state and target state
        String start = builder.toString();
        System.out.println(bfs(start));
    }
    private static int bfs(String start) {
        String end = "12345678x";
        // Treat each state(String) as a vertex of the graph.
        Deque<String> queue = new LinkedList<>();
        Map<String, Integer> distance = new HashMap<>(); // <state, distance from the start point>
        int[][] move = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}}; // Move 1 step in 3x3 grid.(4 directions)
        queue.offerLast(start);
        distance.put(start, 0);
        while (!queue.isEmpty()) {
            String curState = queue.pollFirst();
            int curDist = distance.get(curState);
            if (curState.equals(end)) return curDist;
            int k = curState.indexOf("x");
//            System.out.println("curState=" + curState + "  k=" + k);
            int curX = k / 3, curY = k % 3;
            for (int i = 0; i < move.length; ++ i) {
                int nextX = curX + move[i][0];
                int nextY = curY + move[i][1];
                if (nextX < 3 && nextX >= 0 && nextY < 3 && nextY >= 0) {
                    char[] curStateArr = curState.toCharArray();
                    swap(curStateArr, k, nextX * 3 + nextY);
                    String newState = new String(curStateArr);
                    if (!distance.containsKey(newState)) {
                        distance.put(newState, curDist + 1);
                        queue.offerLast(newState);
                    }
                }
            }
        }
        return -1;
    }
    private static void swap(char[] s, int i, int j) {
         char temp = s[i]; s[i] = s[j]; s[j] = temp;
    }
}

最短路问题

m为边数，n为顶点数。
稠密图（边数多，一般m和n^2是一个级别）使用朴素Dijkstra，否则使用堆优化版本。
重点：如何将问题抽象为图的点和边，抽象为最短路问题。
无向图是特殊的有向图，遇到无向边时，用两个反向有向边代替。
朴素Dijkstra
```java import java.io.*; import java.util.Arrays;

public class Main { static int N = 510, INF = 0X3f3f3f3f, n, m; // 数据范围：点数n<=500；定义无穷大INF；实际的点数n和边数m static int[][] g = new int[N][N]; // 邻接矩阵（适合存稠密图） static int[] distTo = new int[N]; // distTo[i] = 从起点到点i的最短距离 static boolean[] st = new boolean[N]; // st[i] = distTo[i]是否为已经确定的最小距离

public static void main(String[] args) throws IOException {
    // 输入点数n和边数m
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String[] ss = reader.readLine().split(" ");
    n = Integer.parseInt(ss[0]); m = Integer.parseInt(ss[1]);
    // 初始化邻接矩阵：g[i][i] = 0，其他为INF。（两点间不存在边等价于距离无穷大）
    for (int i = 0; i < n; ++ i) {
        Arrays.fill(g[i], INF);
        g[i][i] = 0;
    }
    // 初始化题目给出的m条边
    while (m -- > 0) {
        ss = reader.readLine().split(" ");
        int v1 = Integer.parseInt(ss[0]), v2 = Integer.parseInt(ss[1]), e = Integer.parseInt(ss[2]);
        g[v1][v2] = Math.min(g[v1][v2], e); // 题目可能出现重边，要取最小的边
    }
    int t = dijkstra();
    // 输出结果
    BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    if (t == INF) writer.write("-1");
    else writer.write(t + " ");
    writer.flush();
}

private static int dijkstra() {
    // 初始化distTo数组，从起点到起点的距离为0，到其他点的距离为无穷大
    Arrays.fill(distTo, INF);
    distTo[1] = 0;
    // 每次将一个点加入s集合，即确定其离起点的最小距离，然后让其他点通过这个点，更新其最小距离。
    for (int i = 0; i < n; ++ i) {
        // 1. 找到当前不在集合s中，且距离最近的点minV
        int minV = -1; // minV初始化为-1的意义是区分出未赋值的状态
        for (int j = 1; j <= n; ++ j) {
            if (!st[j] && (minV == -1 || distTo[j] < distTo[minV]))
                minV = j;
        }
        // 2. 此时minV的最小距离已经确定，将minV加入s集合中
        st[minV] = true;
        // 3. 用minV更新其他点的距离，即比较distTo[i]与distTo[minV] + w（w为minV到i的权重）
        for (int j = 1; j <= n; ++ j)
            distTo[j] = Math.min(distTo[j], distTo[minV] + g[minV][j]);
    }
    return distTo[n];
}

}

```

搜索与图论

图