图论|图的构造、图的遍历方式、DFS98. 所有可达路径；海岛数量 岛屿最大面积 101. 孤岛的总面积

前言

图论基础

在有向图中，每个节点有出度和入度。
出度：从该节点出发的边的个数。
入度：指向该节点边的个数

该无向图中 节点1、节点2、节点5 构成的子图就是 该无向图中的一个连通分量，该子图所有节点都是相互可达到的。

同理，节点3、节点4、节点6 构成的子图 也是该无向图中的一个连通分量。

那么无向图中 节点3 、节点4 构成的子图 是该无向图的联通分量吗？

不是！

图的构造

我们如何用代码来表示一个图呢？

一般使用邻接表、邻接矩阵 或者用类来表示。

主要是 朴素存储、邻接表和邻接矩阵

邻接矩阵

邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。
例如： grid[2][5] = 6，表示 节点 2 连接 节点5 为有向图，节点2 指向 节点5，边的权值为6。

如果想表示无向图，即：grid[2][5] = 6，grid[5][2] = 6，表示节点2 与 节点5 相互连通，权值为6。
这种表达方式（邻接矩阵） 在 边少，节点多的情况下，会导致申请过大的二维数组，造成空间浪费。

而且在寻找节点连接情况的时候，需要遍历整个矩阵，即 n * n 的时间复杂度，同样造成时间浪费。

邻接表

邻接表 使用 数组 + 链表的方式来表示。 邻接表是从边的数量来表示图，有多少边 才会申请对应大小的链表。

这里表达的图是：

节点1 指向 节点3 和 节点5
节点2 指向 节点4、节点3、节点5
节点3 指向 节点4
节点4指向节点1
有多少边 邻接表才会申请多少个对应的链表节点。

从图中可以直观看出 使用 数组 + 链表 来表达 边的连接情况 。

邻接表的优点：
对于稀疏图的存储，只需要存储边，空间利用率高
遍历节点连接情况相对容易
缺点：
检查任意两个节点间是否存在边，效率相对低，需要 O(V)时间，V表示某节点连接其他节点的数量。
实现相对复杂，不易理解；

图论的遍历方式

• 深度优先搜索（dfs）
• 广度优先搜索（bfs）
  dfs和bfs二叉树上面分别对应递归遍历和层序遍历

深度优先搜索理论

就是回溯算法：确定递归终止条件回溯

98、所有可达路径ACM

同力扣797. 所有可能的路径

图的存储

思路

dfs三部曲

1. 确定递归函数和参数：
   参数：首先我们dfs函数一定要存一个图，用来遍历的，需要存一个目前我们遍历的节点，定义为x。
2. 终止条件：
   如果x==n，就找到了这个路径path加到result后面
3. 回溯，整体代码
   

方法一 邻接矩阵

邻接矩阵：n+1*n+1，为了使得下标和图节点元素是对应的

def dfs(graph,x,n,path,result):
    if x == n:
        result.append(path[:])
        return 
    for i in range(1,n+1):
        if graph[x][i] != 0:
            path.append(i)
            dfs(graph,i,n,path,result)
            path.pop()
    return 

if __name__ == "__main__":
    n,m = map(int,input().split())
    # print(n,m)
    graph = [[0] * (n+1) for _ in range(n+1)]#图
    for _ in range(m):
        s,t = map(int,input().split())
        graph[s][t] = 1
    result = []
    dfs(graph,1,n,[1],result)
    if not result: print(-1)
    else:
        for ele in result:
            print(" ".join(map(str,ele)))
        

方法二 邻接表

from collections import defaultdict
def dfs(graph,x,n,path,result):
    if x == n:
        result.append(path[:])
        return 
    for ele in graph[x]:
        if ele != 0:
            path.append(ele)
            dfs(graph,ele,n,path,result)
            path.pop()
    return 

if __name__ == "__main__":
    n,m = map(int,input().split())
    # print(n,m)
    graph = defaultdict(list)#创一个list类型的邻接表
    for _ in range(m):
        s,t = map(int,input().