{ }codelper

学习 › Java

算法 · 32

图与深度优先搜索

记下谁和谁相连，再把能到的地方一个不漏地走一遍。

图是由点（人、村子、房间）和连接它们的线（朋友关系、路、门）组成的数据。
下面的例子读入一对对朋友，为每个人建一个朋友列表，然后输出从 1 号出发顺着朋友关系走到各人的顺序，以及把能互相到达的人归在一起后共有几个群。

import java.util.ArrayDeque;import java.util.ArrayList;import java.util.Scanner; public class Main {    static ArrayList<ArrayList<Integer>> adj = new ArrayList<>(); // adj.get(v) = v번의 친구들    static boolean[] seen;    static StringBuilder order = new StringBuilder();     // 재귀: v에 표시하고, 안 가 본 친구가 나오면 바로 그쪽으로 들어가요    static void dfs(int v) {        seen[v] = true;        order.append(order.length() > 0 ? " " : "").append(v);        for (int w : adj.get(v)) {            if (!seen[w]) dfs(w);        }    }     public static void main(String[] args) {        Scanner sc = new Scanner(System.in);        int n = sc.nextInt(), m = sc.nextInt();        for (int v = 0; v <= n; v++) adj.add(new ArrayList<>()); // 빈 목록을 사람마다 하나씩 새로        for (int i = 0; i < m; i++) {            int a = sc.nextInt(), b = sc.nextInt();            adj.get(a).add(b); // 서로 친구라 양쪽에 넣어요            adj.get(b).add(a);        }         seen = new boolean[n + 1];        dfs(1);        System.out.println(order);         // 같은 탐색을 스택으로: 아직 안 본 사람에서 시작할 때마다 무리가 하나        seen = new boolean[n + 1];        int groups = 0;        for (int s = 1; s <= n; s++) {            if (seen[s]) continue;            groups++;            seen[s] = true;            ArrayDeque<Integer> stack = new ArrayDeque<>();            stack.push(s);            while (!stack.isEmpty()) {                int v = stack.pop();                for (int w : adj.get(v)) {                    if (!seen[w]) {                        seen[w] = true;                        stack.push(w);                    }                }            }        }        System.out.println(groups);    }}
stdin
7 5
1 2
1 3
2 4
3 4
5 6
stdout
1 2 4 3
3

要点

  • 输入通常是一对对“a b”。
    把它们改成每个人的邻居列表 adj[v]（邻接表）。
    这样不用再翻那些对子，就能马上知道 v 的邻居是谁。
    如果关系是双向的，要在 adj[a] 里放 b，也在 adj[b] 里放 a。
  • 编号从 1 开始时，开 n + 1 个位置，0 号位置空着不用。
    这样编号可以直接当下标。
  • 深度优先搜索（DFS）在当前位置做上已访问的标记（seen），一遇到没去过的邻居就马上进去。
    无处可去时退回来，再看剩下的邻居。
    例子的 dfs(v) 只接收编号 v，adj、seen、order 放在函数外面，大家共用。
    例子里 1 号的朋友是 2 号和 3 号，但进了 2 号就顺势走到 4 号，之后才去看 3 号，所以顺序是 1 2 4 3。
  • 因为有标记，每个人只进去一次，每条朋友关系只从两头各看一次。
    所以工作量就是人数加上对子的数量。
  • 也可以不用递归，自己用一个栈。
    先放入起点，然后重复到栈空为止：取出一个，把它没去过的邻居做上标记并放进去。
    访问顺序可能不同（例子用栈走是 1 3 4 2），但能到的人是一样的。
  • 每次从一个还没有标记的人重新开始搜索，就多一个群。
    例子里是 {1, 2, 3, 4}、{5, 6}、{7}，所以是 3。

各语言的写法

Pythonadj = [[] for _ in range(n + 1)]，adj[a].append(b)。
栈就是列表的 append 和 pop()
JavaScriptArray.from({ length: n + 1 }, () => [])，adj[a].push(b)。
栈就是数组的 push 和 pop()
TypeScript和 JavaScript 一样。
类型是 number[][]。
stack.pop() 的类型是 number | undefined，所以在已经确认栈不空的地方写 stack.pop()!
Java先往 ArrayList<ArrayList<Integer>> 里 add n + 1 个空的 ArrayList，再 adj.get(a).add(b)。
栈用 ArrayDeque 的 push 和 pop
C#new List<int>[n + 1] 的每个位置都是 null，要逐个放入 new List<int>()。
然后 adj[a].Add(b)。
栈用 Stack<int> 的 Push 和 Pop
C++std::vector<std::vector<int>> adj(n + 1) — 会得到 n + 1 个各自独立的空 vector。
adj[a].push_back(b)。
栈用 vector 的 push_back、back()、pop_back()
C没有会变长的列表。
用 int adj[MAX][MAX] 加上邻居个数 deg[v]，用 adj[a][deg[a]++] = b 放入。
栈也用数组加一个下标 top 来做
Craykon新列表(n + 1, []) 会在每个位置建一个各自独立的空列表。
adj[a].添加(b)，邻居用 遍历 (w 在 adj[v])。
栈用列表的末尾：用 stack.添加(w) 放入，读 stack[stack.数量 - 1]，再用 stack.按位置移除(stack.数量 - 1) 取走

常见错误

只建了数组，没有往里面放列表Java · C#

List<int>[] adj = new List<int>[3];
adj[1].Add(2);

→ NullReferenceException — 刚建好的数组每个位置都是 null。在 Java 里用 new ArrayList[3] 建，也同样会因 NullPointerException 停下

使用前先用循环给每个位置放入 adj[v] = new List<int>();（Java 用 new ArrayList<>()）。

忘了做已访问的标记

void dfs(int v) {
    order.push_back(v);
    for (int w : adj[v]) dfs(w);
}

→ 只要 1 号和 2 号是朋友，就会 1 → 2 → 1 → 2 … 无休止地进去，直到栈溢出，以 SIGSEGV 崩溃。犯同样的错，Python 以 RecursionError 停下，JavaScript 是 RangeError，Java 是 StackOverflowError，C# 输出 Stack overflow. 后崩溃，Craykon 是“函数调用层次太深，已停止”

一进去就用 seen[v] = true 做标记，并且只进入没有标记的邻居。

用 [[]] * n 建邻居列表Python · JavaScript · TypeScript

adj = [[]] * 3
adj[1].append(2)
print(adj)

→ [[2], [2], [2]] — 三个位置指向的是同一个空列表，所以加给 1 号的朋友出现在所有人那里。JavaScript 的 new Array(3).fill([]) 也一样

每个位置都新建一个：[[] for _ in range(n + 1)]、Array.from({ length: n + 1 }, () => [])。

各语言的差异
递归的 DFS 写起来短，但如果人们连成长长的一条线，它就会进到那么深。
在评测机上，例子的 Python 代码能解 900 人连成一线的输入，到 1,100 人就因 RecursionError 停下；Craykon 的代码能解 1,100 人，到 5,000 人停下。
如果 n 可能超过几千，一开始就用栈来写。

练习题

  1. 照着岔路纸条走8P0380
  2. 捉迷藏里找人者走过的路8P0377
  3. 朋友圈8P0118
  4. 折叠的评论串的行号8P0292
  5. 共同好友最多的人8P0293
  6. 只重做过期的文件8P0326
  7. 边捡钥匙边摸索的洞穴探险8P0190
  8. 庆典准备工作的宽裕时间8P0303