图论基础

图论基础

前言

图的分类：

• 有向图 a->b
• 无向图 a->b, b->a

下面考虑有向图的存储

• 邻接矩阵。适用于稠密图
• 邻接表。适用于稀疏图

代码实现

邻接矩阵

就是开辟一个 $n\times n$ 的二维矩阵，$A[i][j]=1$ 代表存在一个从顶点 $i$ 指向顶点 $j$ 的有向边。

如果图的边是带权值的，则 $A[i][j] = val$ 代表的是边 $Edge<i\to j>$ 的权值

邻接矩阵的空间复杂度大

查询两个顶点之间是否存在边的时间复杂度是 $\Omicron(1)$ 的，查询一个顶点相连接的所有顶点，是 $\Omicron (n)$ 的

代码略过。一般不用。

邻接表

基本原理

为每一个顶点创建一个单链表

单链表存的是跟这个顶点相连的顶点编号。

代码实现

数组模拟链表

static final int N = (int)1e5+10;

static final int M = 2 * N;

int idx = 0 这里的idx同前缀树，代表全局唯一“地址”

int[] e = new int[M]; 同模拟单链表，存储着每个链表节点的值，这里为图中顶点的编号

int[] ne = new int[M]; 存储的是：下一个链表节点的“地址”

int[] h = new int[N]; 存储的是：每个图中顶点对应的单链表，头节点的“地址”。h[u]中，u代表着图中顶点编号

增加一条边

为顶点 $A$ 增加一条边 $Edge<A\to B>$ ，顶点 $B$ 的值为 $val$

void add(int A, int val) {
    e[idx] = val;
    ne[idx] = h[A];
    h[A] = idx++;
}

使用JDK工具类

使用哈希表存储<每个顶点，对应单链表>键值对，以实现 $\Omicron(1)$ 读取，单链表用 ArrayList<>() 实现即可

Map<Integer, List<Integer>> graph = new HashMap<>();

增加一条边

BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int i = 0; i < n - 1; ++i) {
    String[] tmp = cin.readLine().split(" ");
    int a = Integer.parseInt(tmp[0]), b = Integer.parseInt(tmp[1]);
    graph.computeIfAbsent(a, key-> new ArrayList<>()).add(b); // 添加一条 a->b 的边
}

关于 computeIfAbsent() 方法，参见官方文档 Oracle java8 api/HashMap

树的深度优先搜索

$\text{DFS}$ ，还会创建一个布尔数组 $\text{visited[i]}$ ，用来标记一个顶点是否被访问过

boolean[] visited = new boolean[N];
// u为顶点的编号
void dfs(int u) {
    visited[u] = true;
    for (int i = h[u]; i != -1; i = ne[i]) {
        int v = e[i];
        if (!visited[v]) dfs(v);
    }
}

例题

acwing 846. 树的重心

什么是重心？

举个🌰

图中顶点 $4$ ，去掉 $4$ 之后剩下三个连通块，分别是3-9,6,8,5-2-1-7，点数最大是5

思路

可以利用深度优先搜索，找出每个顶点的子树的点的数量。

然后将以下几部分进行比较

• $u$ 点的每个子树的节点数。例如3-9的节点数为2，6的节点数为1
• 除去 $u$ 为根的树之外的，图中剩下的连通块的节点数，例如8,5-2-1-7的节点数为5

经过比较，删除 $4$ 后，剩余各个连通块中节点数最大值为5。

具体代码

import java.util.*;
import java.io.*;

class Main{
    static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
    static BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
    static final int N = 100010, M = N * 2;
    static int[] h = new int[N];
    static int[] e = new int[M];
    static int[] ne = new int[M];
    static boolean[] st = new boolean[N];
    static int idx = 0;
    static int ans = N;
    static int nn;
    public static void main(String[] args) throws Exception {
        idx = 0;
        Arrays.fill(h, -1);
        ans = N;
        int n = Integer.parseInt(cin.readLine());
        nn = n;
        int a, b;
        for (int i = 0; i < n - 1; ++i) {
            String[] tmp = cin.readLine().split(" ");
            a = Integer.parseInt(tmp[0]);
            b = Integer.parseInt(tmp[1]);
            add(a, b); 
            add(b, a);
        }
        
        dfs(1);
        
        log.write(String.valueOf(ans));
        
        log.flush();
        log.close();
        cin.close();
    }
    static void add(int u, int val) {
        e[idx] = val;
        ne[idx] = h[u];
        h[u] = idx++;
    }
    static int dfs(int u) throws Exception {
        st[u] = true;
        int res = 0, sum = 1;
        for (int i = h[u]; i != -1; i = ne[i]) {
            int v = e[i];
            if (!st[v]) {
                int s = dfs(v);
                res = Math.max(s, res); // 找出子树中最大的节点数
                sum += s;
            }
        }
        res = Math.max(res, nn - sum); // 除去u点为根的树之外的连通块的节点数
        // log.write(sum + "\n");
        ans = Math.min(ans, res);
        return sum;
    }
}

模拟过程参见。

树的广度优先搜索

直接看例题 acwing 847. 图中点的层次

广度优先搜索图，也是有固定模板的。

Y总板书

核心代码

int hh = 0, tt = 0;
q[0] = 1; // 将1号点入队
Arrays.fill(d, -1); // 距离数组初始化为-1
d[1] = 0;
while (hh <= tt) {
    int cur = q[hh++];
    for (int i = h[cur]; i != -1; i = ne[i]) {
        int v = e[i];
        if (d[v] == -1) { // ！=-1为是否访问过该点的标志
            d[v] = d[cur] + 1;
            q[++tt] = v;
        }
    }
}
System.out.println(d[n]);

---

📔博文图谱

提及本博文的链接

• 图论：建图&搜索