图算法
洪笳淏 Lv4
 2021-09-14 15:08:00      

图论基础

图的逻辑结构和具体实现

  1. 图的逻辑结构

avatar

  为了方便研究图，我们将图可以抽象为下面的形式：

1
2
3
4
type Vertex struct {
  	id					int
  	neighbors		[]*Vertex
}

  可见，这个结构和多叉树节点是一样的。所以可以认为图是比较特殊的多叉树。不过呢，上面的这种实现是「逻辑上的」，实际上我们很少用这个 Vertex 类实现图，而是用常说的邻接表和邻接矩阵来实现。

  1. 具体实现方式

avatar

  • 邻接表：邻接表很直观，我把每个节点 x 的邻居都存到一个列表里，然后把 x 和这个列表关联起来，这样就可以通过一个节点 x 找到它的所有相邻节点。
  • 邻接矩阵：邻接矩阵是一个二维布尔数组，将其称为matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true（上图中绿色的方格代表 true）。如果想找节点 x的邻居，去扫一圈 matrix[x][..] 就行了。
  1. 邻接表和邻接矩阵的优劣
  • 邻接表
    • 好处是占用的空间少。
    • 坏处是邻接表无法快速判断两个节点是否相邻。
  • 邻接矩阵
    • 好处是可以快速判断两个节点是否相邻。
    • 坏处是占用空间大。

更复杂的图

  • 有向加权图
    • 如果使用邻接表，我们不仅仅存储某个节点 x 的所有邻居节点，还存储 x 到每个邻居的权重。
    • 如果使用邻接矩阵，matrix[x][y] 不再是布尔值，而是一个 int 值，0 表示没有连接，其他值表示权重。
  • 无向图
    • 所谓的「无向」，也等同于「双向」。
    • 如果连接无向图中的节点 x 和 y，把 matrix[x][y] 和 matrix[y][x] 都变成 true。
    • 如果使用邻接表，则list[x]和list[y]中各自填入y 和x。

图的遍历

  图和多叉树最大的区别是，图是可能包含环的，你从图的某一个节点开始遍历，有可能走了一圈又回到这个节点。所以，如果图包含环，遍历框架就要一个 visited 数组进行辅助：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
graph *Vertex
visited bool

func traverse(graph *Vertex, s int) {
  	if visited[s] == true {
    	return  // 经过节点s
  	}
  
  	visited[s] = true
  	for _,v := range s.neighbor {
    	traverse(graph, s)
  	}
  	visited[s] = false
}

  这个 visited 数组的操作很像回溯算法做「做选择」和「撤销选择」，区别在于位置，回溯算法的「做选择」和「撤销选择」在 for 循环里面，而对 visited 数组的操作在 for 循环外面。在 for 循环里面和外面唯一的区别就是对根节点的处理。对于这里「图」的遍历，我们应该把 visited 的操作放到 for 循环外面，否则会漏掉起始点的遍历。

797. 所有可能的路径

给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）

二维数组的第 i 个数组中的单元都表示有向图中 i 号节点所能到达的下一些节点，空就是没有下一个结点了。

示例 1

avatar

1
2
3
输入：graph = [[1,2],[3],[3],[]]
输出：[[0,1,3],[0,2,3]]
解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3

示例 2：

avatar

1
2
输入：graph = [[4,3,1],[3,2,4],[3],[4],[]]
输出：[[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]

示例 3：

1
2
输入：graph = [[1],[]]
输出：[[0,1]]

示例 4：

1
2
输入：graph = [[1,2,3],[2],[3],[]]
输出：[[0,1,2,3],[0,2,3],[0,3]]

示例 5：

1
2
输入：graph = [[1,3],[2],[3],[]]
输出：[[0,1,2,3],[0,3]]
1
2
3
4
5
6
7
8
提示：

n == graph.length
2 <= n <= 15
0 <= graph[i][j] < n
graph[i][j] != i（即，不存在自环）
graph[i] 中的所有元素 互不相同
保证输入为 有向无环图（DAG）

解题思路：

  从0为起点开始遍历图，将遍历到的每个节点加入到辅助数组path中，当遍历到节点值为n-1时停止遍历，将path保存的路径拷贝到输出结构res中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func allPathsSourceTarget(graph [][]int) [][]int {
    res := make([][]int,0)
    path := make([]int,0)
    travel(path, graph, &res, 0)
    return res
}

func travel(path []int, graph [][]int, res *[][]int, start int) {

    path = append(path,start)
    n := len(graph)-1
    if start == n {
        dst := make([]int,len(path))
        copy(dst,path) // 由于在回溯的时候path会动态变化，所以要重新拷贝后传入res
        *res = append(*res,dst)
        return
    }

    for _,v := range graph[start] {
        travel(path, graph, res, v)
    }
}

有向图的环检测

207. 课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1。

在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。

  • 例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

1
2
3
输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成​课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。
1
2
3
4
5
6
7
提示：

1 <= numCourses <= 105
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= ai, bi < numCourses
prerequisites[i] 中的所有课程对 互不相同

解题思路：

  什么时候无法修完所有课程？当存在循环依赖的时候。其实这种场景在现实生活中也十分常见，比如我们写代码 import 包也是一个例子，必须合理设计代码目录结构，否则会出现循环依赖，编译器会报错，所以编译器实际上也使用了类似算法来判断你的代码是否能够成功编译。

  看到依赖问题，首先想到的就是把问题转化成「有向图」这种数据结构，只要图中存在环，那就说明存在循环依赖。具体来说，我们首先可以把课程看成「有向图」中的节点，节点编号分别是 0, 1, ..., numCourses-1，把课程之间的依赖关系看做节点之间的有向边。

  比如说必须修完课程 1 才能去修课程 3，那么就有一条有向边从节点 1 指向 3。所以我们可以根据题目输入的 prerequisites 数组生成一幅类似这样的图：

avatar

  如果发现这幅有向图中存在环，那就说明课程之间存在循环依赖，肯定没办法全部上完；反之，如果没有环，那么肯定能上完全部课程。所以第一步，我们要讲本题的这种依赖关系转换成图。

  • 先写一个建图函数
1
2
3
4
5
6
7
8
9
func buildGraph(numCourses int, prerequisites [][]int) [][]int {
    graph := make([][]int,numCourses)
    for _,v := range prerequisites {
        from := v[1]
        to := v[0]
        graph[from] = append(graph[from], to)
    }
    return graph
}
  • 可以把 traverse 看做在图中节点上游走的指针，只需要再添加一个布尔数组 onPath 记录当前 traverse 经过的路径。完整代码如下：
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
func canFinish(numCourses int, prerequisites [][]int) bool {
    graph := buildGraph(numCourses, prerequisites)
    onPath := make([]bool,numCourses)
    visited := make([]bool,numCourses)
    isCycle := false
    
    var traverse func(int)
    traverse = func(s int) {
        if onPath[s] == true { // 发现环
            isCycle = true
        }

        if visited[s] || onPath[s] { // 若是遍历过的节点或是存在于环内的节点，直接回溯
            return
        }

        // 前序遍历代码
        visited[s] = true
        onPath[s] = true

        for _,v := range graph[s] {
            traverse(v)
        }

        // 后序遍历代码
        onPath[s] = false // 在回溯的过程中将遍历过的节点标记为无环状态
    }

    for i:=0; i<numCourses; i++ {  // 遍历图中所有节点
        traverse(i)
    }

    return !isCycle
}

func buildGraph(numCourses int, prerequisites [][]int) [][]int {
    graph := make([][]int,numCourses)
    for _,v := range prerequisites {
        from := v[1]
        to := v[0]
        graph[from] = append(graph[from], to)
    }
    return graph
}

拓扑排序（无环图的后续遍历的反转）

210. 课程表 II

现在你总共有 n 门课需要选，记为 0 到 n-1。

在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

1
2
3
输入: 2, [[1,0]] 
输出: [0,1]
解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

1
2
3
4
输入: 4, [[1,0],[2,0],[3,1],[3,2]]
输出: [0,1,2,3] or [0,2,1,3]
解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
     因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3]。

说明:

  1. 输入的先决条件是由边缘列表表示的图形，而不是邻接矩阵。详情请参见图的表示法。
  2. 你可以假定输入的先决条件中没有重复的边。

提示:

  • 这个问题相当于查找一个循环是否存在于有向图中。如果存在循环，则不存在拓扑排序，因此不可能选取所有课程进行学习。
  • 拓扑排序也可以通过 BFS 完成。

解题思路：

  这道题就是上道题的进阶版，不是仅仅让你判断是否可以完成所有课程，而是进一步让你返回一个合理的上课顺序，保证开始修每个课程时，前置的课程都已经修完。如果把课程抽象成节点，课程之间的依赖关系抽象成有向边，那么这幅图的拓扑排序结果就是上课顺序。首先，我们先判断一下题目输入的课程依赖是否成环，成环的话是无法进行拓扑排序的，所以我们可以复用上一道题的主函数。将后序遍历的结果进行反转，就是拓扑排序的结果。为什么后序遍历的反转结果就是拓扑排序呢？后序遍历的这一特点很重要，之所以拓扑排序的基础是后序遍历，是因为一个任务必须在等到所有的依赖任务都完成之后才能开始开始执行。你把每个任务理解成二叉树里面的节点，这个任务所依赖的任务理解成子节点，那你是不是应该先把所有子节点处理完再处理父节点？这是不是就是后序遍历？所以只需要在遍历节点的时候使用一个postorder数组存储后续遍历结果即可。

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
54
55
56
57
58
func findOrder(numCourses int, prerequisites [][]int) []int {
    postorder := make([]int,0)
    if canFinish(numCourses, prerequisites, &postorder) == false {
        return []int{} // 先判断是否有环，有环的话直接输出空数组
    }
    
    res := make([]int,numCourses)
    for i:=0; i<numCourses; i++ { // 无环的话将后续遍历的结果反转即可
        res[i] = postorder[numCourses-i-1]
    }
    return res
}

func canFinish(numCourses int, prerequisites [][]int, postorder *[]int) bool {
    graph := buildGraph(numCourses, prerequisites)
    onPath := make([]bool,numCourses)
    visited := make([]bool,numCourses)
    isCycle := false
    
    var traverse func(int)
    traverse = func(s int) {
        if onPath[s] == true { // 发现环
            isCycle = true
        }

        if visited[s] || onPath[s] { // 若是遍历过的节点或是存在于环内的节点，直接回溯
            return
        }

        // 前序遍历代码
        visited[s] = true
        onPath[s] = true

        for _,v := range graph[s] {
            traverse(v)
        }

        // 后序遍历代码
        onPath[s] = false // 在回溯的过程中将遍历过的节点标记为无环状态
        *postorder = append(*postorder,s) // 存储后续遍历的结果
    }

    for i:=0; i<numCourses; i++ {  // 遍历图中所有节点
        traverse(i)
    }

    return !isCycle
}

func buildGraph(numCourses int, prerequisites [][]int) [][]int { // 生成图结构
    graph := make([][]int,numCourses)
    for _,v := range prerequisites {
        from := v[1]
        to := v[0]
        graph[from] = append(graph[from], to)
    }
    return graph
}
  • Post title：图算法
  • Post author：洪笳淏
  • Create time：2021-09-14 15:08:00
  • Post link：https://jiahaohong1997.github.io/2021/09/14/图算法/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments