算法长征（12）图

发表于 更新于 分类于 ， 阅读次数： 本文字数： 2.6k 阅读时长 ≈ 5 分钟

图论算法从入门到放下

https://leetcode.cn/circle/discuss/FyPTTM/

主要内容一览

graph_mind.png

岛屿问题

给定一个由 0 和 1 组成的非空二维数组 grid ，用来表示海洋岛屿地图。一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

示例 1:

img

输入: grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]] 输出: 6 解释: 对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        # 深度优先搜索 空间复杂度o(m*n)
        m, n = len(grid), len(grid[0])
        res = 0
        def dfs(x, y) -> int:
            s = 1
            grid[x][y] = 0
            for i, j in [(x - 1, y), (x, y - 1), (x + 1, y), (x, y + 1)]:
                if i < 0 or j < 0 or i == m or j == n or grid[i][j]!=1:
                    continue
                s += dfs(i, j)
            return s

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    res = max(res, dfs(i, j))
        return res

有 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 = [[] for _ in range(n)]
        for x, y, time in times:
            g[x - 1].append((y - 1, time))

        dist = [float('inf')] * n
        dist[k - 1] = 0
        q = [(0, k - 1)]
        while q:
            time, x = heapq.heappop(q)
            if dist[x] < time:
                continue
            for y, time in g[x]:
                if (d := dist[x] + time) < dist[y]:
                    dist[y] = d
                    heapq.heappush(q, (d, y))

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

存在一个 无向图 ，图中有 n 个节点。其中每个节点都有一个介于 0 到 n - 1 之间的唯一编号。给定一个二维数组 graph ，表示图，其中 graph[u] 是一个节点数组，由节点 u 的邻接节点组成。形式上，对于 graph[u] 中的每个 v ，都存在一条位于节点 u 和节点 v 之间的无向边。

二分图 定义：如果能将一个图的节点集合分割成两个独立的子集 A 和 B ，并使图中的每一条边的两个节点一个来自 A 集合，一个来自 B 集合，就将这个图称为 二分图 。

示例 1：

img

输入：graph = [[1,2,3],[0,2],[0,1,3],[0,2]] 输出：false 解释：不能将节点分割成两个独立的子集，以使每条边都连通一个子集中的一个节点与另一个子集中的一个节点。

  • 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
class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 广度优先遍历 [推荐]
        n = len(graph)
        uncolor, red, green = 0, 1, 2
        color = [0] * n
        for i in range(n):
            if color[i] == uncolor:
                color[i] = red
                q = deque([i])
                while q:
                    node = q.popleft()
                    nei = green if color[node] == red else red
                    for j in graph[node]:
                        if color[j] == uncolor:
                            color[j] = nei
                            q.append(j)
                        elif color[j] != nei:
                            return False
        return True
    def isBipartite(self, graph: List[List[int]]) -> bool:
        # 深度优先遍历 【不推荐】
        def dfs(i: int, c: int):
            nonlocal res
            nei = green if c == red else red
            for j in graph[i]:
                if color[j] == uncolor:
                    color[j] = nei
                    dfs(j, nei)
                elif color[j] != nei:
                    res = False

        n = len(graph)
        uncolor, red, green = 0, 1, 2
        color = [0] * n
        res = True
        for i in range(n):
            if color[i] == uncolor and res:
                dfs(i, red)
        return res
    
    # def isBipartite(self, graph: List[List[int]]) -> bool:
    #     # 并查集 【了解】