CS61B 课程笔记（DISC 11 Graphs)

1. 图的表示

1.1 邻接矩阵和邻接表

对于给定的图，可以用邻接矩阵和邻接表来表示。

邻接矩阵:

     A B C D E F G
A [  0 1 0 1 0 0 0 ]
B [  0 0 1 0 0 0 0 ]
C [  0 0 0 0 0 1 0 ]
D [  0 1 0 0 1 1 0 ]
E [  0 0 0 0 0 1 0 ]
F [  0 0 0 0 0 0 0 ]
G [  0 0 0 0 0 1 0 ]

邻接表:

A: {B, D}
B: {C}
C: {F}
D: {B, E, F}
E: {F}
F: {}
G: {F}

无向图的变化:

对于无向图，邻接矩阵和邻接表的每个边都要双向记录。例如，若有边 (A, B)，则在矩阵中 A 和 B 的位置均为 1。

2. 图的遍历

1.2 深度优先搜索（DFS）和广度优先搜索（BFS）

DFS 前序遍历: ABCFDE
DFS 后序遍历: FCBEDA
BFS 遍历: ABDCEF

3. 拓扑排序

1.3 有效拓扑排序

根据提示，可以使用逆后序遍历得到一个有效的拓扑排序。例如：

1	G - A - D - E - B - C - F

在这个排序中，G可以放在任何地方，但不能放在F之后，因为F有一个入边。

4. 图算法设计

2.1 判断图是否为二分图

算法:

使用DFS或BFS进行遍历，标记起始顶点为U，其子节点为V，然后继续标记。
如果在遍历中发现一个节点应该被标记为U但已标记为V，说明图不是二分图。
对于不连通的图，需对每个连通分量重复这一过程。

时间复杂度: \(O(E + V)\)

2.2 查找有向图中的最短回路

算法:

对于源顶点s，运行BFS以找到每个顶点的最短路径。
遍历所有顶点，如果某个顶点v有边返回到s，则回路长度为distTo(v) + 1。
对于整个图，需对每个顶点调用此子程序。

时间复杂度: \(O(EV)\)，空间复杂度：\(O(E)\)

2.3 DFS实现中的错误示例

错误实现:

在遍历邻接点之前就标记顶点，可能导致不按照DFS顺序遍历。例如，访问顺序可能为 A - B - C - D，而不是深度优先的顺序。
正确的做法是先访问节点再标记。

Java实现代码

以下是DFS、BFS和拓扑排序的Java代码示例：

import java.util.*;

class Graph {
    private Map<String, List<String>> adjList;

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

    public void addEdge(String source, String destination) {
        this.adjList.putIfAbsent(source, new ArrayList<>());
        this.adjList.putIfAbsent(destination, new ArrayList<>());
        this.adjList.get(source).add(destination);
    }

    // 深度优先搜索
    public void dfs(String start) {
        Set<String> visited = new HashSet<>();
        dfsUtil(start, visited);
    }

    private void dfsUtil(String vertex, Set<String> visited) {
        visited.add(vertex);
        System.out.print(vertex + " ");
        for (String neighbor : adjList.get(vertex)) {
            if (!visited.contains(neighbor)) {
                dfsUtil(neighbor, visited);
            }
        }
    }

    // 广度优先搜索
    public void bfs(String start) {
        Set<String> visited = new HashSet<>();
        Queue<String> queue = new LinkedList<>();
        visited.add(start);
        queue.add(start);
        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            System.out.print(vertex + " ");
            for (String neighbor : adjList.get(vertex)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
    }

    // 拓扑排序
    public void topologicalSort() {
        Map<String, Integer> inDegree = new HashMap<>();
        for (String vertex : adjList.keySet()) {
            inDegree.put(vertex, 0);
        }
        for (List<String> neighbors : adjList.values()) {
            for (String neighbor : neighbors) {
                inDegree.put(neighbor, inDegree.get(neighbor) + 1);
            }
        }

        Queue<String> queue = new LinkedList<>();
        for (Map.Entry<String, Integer> entry : inDegree.entrySet()) {
            if (entry.getValue() == 0) {
                queue.add(entry.getKey());
            }
        }

        while (!queue.isEmpty()) {
            String vertex = queue.poll();
            System.out.print(vertex + " ");
            for (String neighbor : adjList.get(vertex)) {
                inDegree.put(neighbor, inDegree.get(neighbor) - 1);
                if (inDegree.get(neighbor) == 0) {
                    queue.add(neighbor);
                }
            }
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph();
        graph.addEdge("A", "B");
        graph.addEdge("A", "D");
        graph.addEdge("B", "C");
        graph.addEdge("C", "F");
        graph.addEdge("D", "B");
        graph.addEdge("D", "E");
        graph.addEdge("D", "F");
        graph.addEdge("E", "F");
        graph.addEdge("G", "F");

        System.out.println("DFS:");
        graph.dfs("A");

        System.out.println("\nBFS:");
        graph.bfs("A");

        System.out.println("\nTopological Sort:");
        graph.topologicalSort();
    }
}