HelloBear

Less is More

0%

图论

Posted on Edited on

本篇文章记录了图的基本知识，图的邻接表表示，深度优先和广度优先遍历，并查集，拓扑排序，最小生成树问题，单源最短路径问题。所有的数据结构和算法都用python语言实现。

图的基本知识

图的基本知识见：数据结构与算法——图论基础与图存储结构_吴师兄学算法

图的表示

图的表示方法主要有数组表示和邻接表表示两种。

数组表示即用n×n的矩阵表示图的连接关系，矩阵中[i,j]值为1表示i节点与j节点相连，为0表示不相连。

邻接表表示则是对于每个节点，存储与它直接相连的节点。

图的遍历

为了介绍图的两种遍历方法，我们直接看这一题：

[Leecode797 所有可能的路径](797. 所有可能的路径 - 力扣（LeetCode） (leetcode-cn.com))

分别用两种方法实现。

深度优先

题目要求一个有向无环图的所有路径，这直接用深度优先+回溯就可以解决，可以把0号节点作为根节点，依次向下深度遍历：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        path = [0]
        ans = []
        n = len(graph)
        def dfs(t,graph,n):
            if path[-1] == n-1:
                ans.append(path[:])
            for i in graph[t]:
                path.append(i)
                dfs(i,graph,n)
                path.pop()
        dfs(0,graph,n)
        return ans

广度优先

类似的，也可以用广度优先算法实现，这里与上面不同点在于，需要记录每一个路径，因此队列里面加入的不是节点值，而是历史的路径，其他的和树里面的层序遍历一样。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        from collections import deque
        dq = deque([[0]])
        ans = []
        while dq:
            size = len(dq)
            for _ in range(size):
                tmp = dq.popleft()
                if tmp[-1] == len(graph)-1:
                    ans.append(tmp)
                for i in graph[tmp[-1]]:
                    dq.append(tmp+[i])
        return ans

并查集（Disjoint Set）

并查集是用来判断一个无向图有没有环的算法。改算法包括两个部分，即findParent部分和Union部分。具体的实现见下方Kruskal 算法部分。

拓扑排序问题

图的拓扑排序问题指的是，针对有向无环图（Directed Acyclic Graph，DAG），找出一个合理的顺序，满足节点之间的先后依赖关系。

满足的性质：

  • 如果图中存在环，那么该图不存在拓扑排序

  • 如果图是有向无环图，那么拓扑排序不止一种

看一道leecode题目：207课程表，判断能否有满足要求的拓扑排序，210.课程表II，这题则要求输出一种排好的顺序。这两题可以合并为一题。

深度优先搜索算法用一个栈来存储课程的选择顺序，针对节点的访问状态，设置了三种表述，分别为0（未访问），1（正在访问），2（访问过），如果在访问的过程中遇到了1，代表了有环，则退出。

动画演示见leecode题解：课程表 - 课程表 - 力扣（LeetCode） (leetcode-cn.com)

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
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
    edges = collections.defaultdict(list)
    visited = [0] * numCourses
    valid = True
    stack = []

    for i in prerequisites:
        edges[i[1]].append(i[0])

    def dfs(i):
        nonlocal valid
        visited[i] = 1
        for j in edges[i]:
            if visited[j] == 0:
                dfs(j)
                if not valid:
                    return
            elif visited[j] == 1:
                valid = False
                return
        visited[i] = 2
        stack.append(i)

    for i in range(numCourses):
        if valid and visited[i] == 0:
            dfs(i)

    return valid

最小生成树

  • 生成树：无向图中，具有该图的 全部顶点 且 边数最少 的连通子图，如下图红色线组成的边，构成一个生成树。
  • 最小生成树：加权无向图中总权重最小的生成树，绿色线组成的边，构成一个最小生成树

切分定理

  • 切分：将图切成两个部分，称之为一个切分，其中(B, A, E)为一个部分，(C, D)为另外一个部分。

  • 横切边：如果一条边连接的两个顶点属于切分的两个部分，这个边称为横切边，(B, C), (A, C), (A, D), (E, D) 均为横切边。

  • 切分定理：在一幅连通加权无向图中，给定任意的切分，如果有一条横切边的权值严格小于所有其他横切边，则这条边必然属于图的最小生成树中的一条边。（证明：一条边+权值最小的边）

Kruskal 算法

  • 将所有边从小到大排序

  • 依次加入到最小生成树中，如果有环就跳过

  • 直到选择了N-1条边

举例：1584. 连接所有点的最小费用 - 力扣（LeetCode） (leetcode-cn.com)

题目要求，将所有点连接起来的最小费用，即最小生成树问题。在最小生成树中，由于需要判断是否有环，因此需要首先实现一个并查集类,这个类有两个属性，即记录parents，以及以及加入的边的个数，两个方法，即查找parent和合并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class SetUnion:
    def __init__(self,n):
        self.parents = [-1] * n
        self.edges = 0

    def findParent(self,index):
        parent = index
        while self.parents[parent] != -1:
            parent = self.parents[parent]
        return parent

    def union(self,index1,index2):
        parent1 = self.findParent(index1)
        parent2 = self.findParent(index2)
        if parent1 == parent2:
            return True
        else:
            self.parents[parent1] = parent2
            self.edges += 1
            return False

有了这个类，就可以实现Kruskal算法了，第一步先计算节点之间的距离（权值，并排序），接着依次加入并查集就可以了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def minCostConnectPoints(self, points: List[List[int]]) -> int:
        def mhd(x1,x2):
            return abs(x1[0]-x2[0]) + abs(x1[1]-x2[1])

        record = {}
        for i in range(len(points)):
            for j in range(i+1,len(points)):
                record[(i,j)] = mhd(points[i],points[j])

        sortedRecord = sorted(record.items(),key = lambda x: x[1])
        disjoinedset = SetUnion(len(points))
        ans = 0
        for items in sortedRecord:
            if not disjoinedset.union(items[0][0],items[0][1]):
                ans += items[1]
            if disjoinedset.edges == len(points)-1:
                return ans
        return ans

注意不能用新加入的节点是否已经被包括来判断是否有环，例如(0,2),(1,3)，这时加入(0,1)，如果根据节点判断则有环，实际没有！

Prim算法

  • 在所有unvisited的节点列表中任意选择一个，加入visited列表

  • 将所有visited列表组成的点作为一个整体，寻找与这个整体相连的边中权值最小的边，将其对应的点加入到visited中，循环

  • visited列表等于N，结束

举例，还是leecode1584题，这次采用Prim算法解。

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
from heapq import *

def dist(x, y):
    return abs(x[0] - y[0]) + abs(x[1] - y[1])

class Solution:

    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        V_connected = set()
        # Edge candidate，最小堆
        E_cand = []
        # 对新加入的节点start，把所有对外的边都加入E_candidate集合
        # 我们不关心边的起始位置，只要关心终结的节点就可以判断该边是不是有效的对外边。所以最小堆中存的是(cost, end节点)
        def adding_edges(start):
            for end in range(len(points)):
                if end not in V_connected:
                    heappush(E_cand, (dist(points[start], points[end]), end))


        V_connected.add(0)
        adding_edges(0)

        min_cost = 0

        while len(V_connected) != len(points):
            cost, end = heappop(E_cand)
            # pop出来的边，如果已经失效，就继续pop
            if end in V_connected:
                continue

            min_cost += cost
            V_connected.add(end)
            adding_edges(end)

        return min_cost

单源最短路径

找到一个图中，到其他所有节点的最短路径。

Dijkstra算法

维护一个长度为节点数目的二维列表，其中每个节点对应于是否被访问、到目标节点的距离大小，从目标节点开始，依次遍历更新。学习：# Dijkstra(迪杰斯特拉)算法理解

为了实现这个算法，首先需要将连接关系转为邻接表表示。随后，遍历所有节点，找到未被访问且距离最小的点，作为此次访问的节点。对于访问的节点，我们需要依次计算当该节点在路径中时，其他所有节点到目标节点的最小距离。当遍历完所有节点后，结束。

743. 网络延迟时间:

要求：有 n 个网络节点，标记为 1到 n。给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    def networkDelayTime(self, times: List[List[int]], n: int, k: int) -> int:
        g = [[float('inf')] * n for _ in range(n)]
        for x, y, time in times:
            g[x - 1][y - 1] = time

        dist = [float('inf')] * n
        dist[k - 1] = 0
        used = [False] * n
        for _ in range(n):
            x = -1
            for y, u in enumerate(used):
                if not u and (x == -1 or dist[y] < dist[x]):
                    x = y
            used[x] = True
            for y, time in enumerate(g[x]):
                dist[y] = min(dist[y], dist[x] + time)

        ans = max(dist)
        return ans if ans < float('inf') else -1

Bellman-Ford算法

总结

本文总结了图论中最为常见一些算法了，每个算法都有详细的实现过程。