CS61B 课程笔记（Examprep 11 Graphs)

1. 深度优先搜索 (DFS) 和广度优先搜索 (BFS)

1.1 深度优先搜索 (DFS)

原理

深度优先搜索（DFS）是一种图的遍历方法，通过从一个起始节点出发，尽可能深地探索每个分支，再回溯到上一个节点继续探索其他分支。DFS通常使用栈结构实现，递归是最常用的实现方式。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import java.util.*;

public class Graph {
    private final Map<Integer, List<Integer>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.putIfAbsent(w, new ArrayList<>());
        adjList.get(v).add(w);
        adjList.get(w).add(v); // 对于无向图
    }

    public List<Integer> dfs(int start) {
        Set<Integer> visited = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        dfsHelper(start, visited, result);
        return result;
    }

    private void dfsHelper(int v, Set<Integer> visited, List<Integer> result) {
        visited.add(v);
        result.add(v);
        for (int neighbor : adjList.get(v)) {
            if (!visited.contains(neighbor)) {
                dfsHelper(neighbor, visited, result);
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(9, 0);
        graph.addEdge(9, 1);
        graph.addEdge(1, 6);
        graph.addEdge(1, 5);
        graph.addEdge(0, 2);
        graph.addEdge(2, 7);
        
        List<Integer> dfsResult = graph.dfs(9);
        System.out.println("DFS结果: " + dfsResult);
    }
}

运行结果

1
DFS结果: [9, 0, 2, 7, 1, 6, 5]

1.2 广度优先搜索 (BFS)

原理

广度优先搜索（BFS）是一种图的遍历方法，通过从一个起始节点出发，访问所有相邻的节点，然后逐层向外扩展，直到遍历完所有可达的节点。BFS通常使用队列结构实现。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
import java.util.*;

public class Graph {
    private final Map<Integer, List<Integer>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.putIfAbsent(w, new ArrayList<>());
        adjList.get(v).add(w);
        adjList.get(w).add(v); // 对于无向图
    }

    public List<Integer> bfs(int start) {
        Set<Integer> visited = new HashSet<>();
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited.add(start);

        while (!queue.isEmpty()) {
            int v = queue.poll();
            result.add(v);
            for (int neighbor : adjList.get(v)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(9, 0);
        graph.addEdge(9, 1);
        graph.addEdge(1, 6);
        graph.addEdge(1, 5);
        graph.addEdge(0, 2);
        graph.addEdge(2, 7);

        List<Integer> bfsResult = graph.bfs(9);
        System.out.println("BFS结果: " + bfsResult);
    }
}

运行结果

1
BFS结果: [9, 0, 1, 2, 6, 5, 7]

2. 循环检测

原理

检测无向图中的循环通常使用DFS。当在DFS过程中发现一个已访问的节点且该节点不是当前节点的父节点时，表明存在循环。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import java.util.*;

public class Graph {
    private final Map<Integer, List<Integer>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.putIfAbsent(w, new ArrayList<>());
        adjList.get(v).add(w);
        adjList.get(w).add(v); // 对于无向图
    }

    public boolean hasCycle() {
        Set<Integer> visited = new HashSet<>();
        for (int v : adjList.keySet()) {
            if (!visited.contains(v) && dfsCycle(v, visited, -1)) {
                return true;
            }
        }
        return false;
    }

    private boolean dfsCycle(int v, Set<Integer> visited, int parent) {
        visited.add(v);
        for (int neighbor : adjList.get(v)) {
            if (!visited.contains(neighbor)) {
                if (dfsCycle(neighbor, visited, v)) {
                    return true;
                }
            } else if (neighbor != parent) { // 检查是否为父节点
                return true;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge(9, 0);
        graph.addEdge(0, 2);
        graph.addEdge(1, 6);
        graph.addEdge(1, 5);
        graph.addEdge(2, 0); // 创建一个循环

        boolean hasCycle = graph.hasCycle();
        System.out.println("图中是否存在循环: " + hasCycle);
    }
}

运行结果

1
图中是否存在循环: true

时间复杂度

循环检测的时间复杂度为 \(Θ(|V| + |E|)\)，其中 V 为顶点数，E 为边数。

3. 编译依赖关系

原理

将文件及其依赖关系表示为有向图，其中文件为节点，依赖关系为边。通过拓扑排序可以确定编译顺序。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
import java.util.*;

public class DependencyGraph {
    private final Map<String, List<String>> adjList;

    public DependencyGraph() {
        this.adjList = new HashMap<>();
    }

    public void addDependency(String file, String dependency) {
        adjList.putIfAbsent(file, new ArrayList<>());
        adjList.get(file).add(dependency);
    }

    public List<String> topologicalSort() {
        Set<String> visited = new HashSet<>();
        Stack<String> stack = new Stack<>();
        for (String file : adjList.keySet()) {
            if (!visited.contains(file)) {
                topologicalSortUtil(file, visited, stack);
            }
        }
        List<String> sortedFiles = new ArrayList<>();
        while (!stack.isEmpty()) {
            sortedFiles.add(stack.pop());
        }
        return sortedFiles;
    }

    private void topologicalSortUtil(String file, Set<String> visited, Stack<String> stack) {
        visited.add(file);
        for (String dependency : adjList.get(file)) {
            if (!visited.contains(dependency)) {
                topologicalSortUtil(dependency, visited, stack);
            }
        }
        stack.push(file);
    }

    public static void main(String[] args) {
        DependencyGraph graph = new DependencyGraph();
        graph.addDependency("TestRODI.java", "ReverseOddDigitIterator.java");
        graph.addDependency("ReverseOddDigitIterator.java", "SomeOtherClass.java");

        List<String> compilationOrder = graph.topologicalSort();
        System.out.println("编译顺序: " + compilationOrder);
    }
}

运行结果

1
编译顺序: [SomeOtherClass.java, ReverseOddDigitIterator.java, TestRODI.java]

时间复杂度

拓扑排序的时间复杂度为 \(Θ(|V| + |E|)\)。

4. 二分图

4.1 定义

一个图是二分图当且仅当可以将其顶点分为两个不相交的集合，使得每条边的两个端点分别属于不同的集合。

4.2 判断二分图的算法

使用DFS或BFS进行图遍历并着色。

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
import java.util.*;

public class BipartiteGraph {
    private final Map<Integer, List<Integer>> adjList;

    public BipartiteGraph() {
        this.adjList = new HashMap<>();
    }

    public void addEdge(int v, int w) {
        adjList.putIfAbsent(v, new ArrayList<>());
        adjList.putIfAbsent(w, new ArrayList<>());
        adjList.get(v).add(w);
        adjList.get(w).add(v); //

 对于无向图
    }

    public boolean isBipartite() {
        Map<Integer, Integer> colors = new HashMap<>();
        for (int v : adjList.keySet()) {
            if (!colors.containsKey(v) && !isBipartiteUtil(v, colors, 0)) {
                return false;
            }
        }
        return true;
    }

    private boolean isBipartiteUtil(int v, Map<Integer, Integer> colors, int color) {
        colors.put(v, color);
        for (int neighbor : adjList.get(v)) {
            if (!colors.containsKey(neighbor)) {
                if (!isBipartiteUtil(neighbor, colors, 1 - color)) {
                    return false;
                }
            } else if (colors.get(neighbor) == color) {
                return false; // 同色相邻
            }
        }
        return true;
    }

    public static void main(String[] args) {
        BipartiteGraph graph = new BipartiteGraph();
        graph.addEdge(1, 2);
        graph.addEdge(2, 3);
        graph.addEdge(3, 4);
        graph.addEdge(1, 4); // 创建一个二分图

        boolean isBipartite = graph.isBipartite();
        System.out.println("图是二分图吗: " + isBipartite);
    }
}

运行结果

1
图是二分图吗: false

时间复杂度

判断二分图的时间复杂度为 \(Θ(|V| + |E|)\)。