1、图论基础

一、图的逻辑结构

图是由边和节点组成的。

img

本质上就是个高级点的多叉树而已，适用于树的 DFS/BFS 遍历算法，全部适用于图。

实际上我们表示一个图一般使用邻接表或者邻接矩阵来实现。

img

img

邻接表很直观，我把每个节点 x 的邻居都存到一个列表里，然后把 x 和这个列表关联起来，这样就可以通过一个节点 x 找到它的所有相邻节点。

邻接矩阵则是一个二维布尔数组，我们权且称为 matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true（上图中绿色的方格代表 true）。如果想找节点 x 的邻居，去扫一圈 matrix[x][..] 就行了。

# 邻接表
# graph[x] 存储 x 的所有邻居节点
graph: List[List[int]]

# 邻接矩阵
# matrix[x][y] 记录 x 是否有一条指向 y 的边
matrix: List[List[bool]]

邻接表：占用空间少但是无法快速判断两个节点是否相邻。但对于邻接矩阵就简单了，只要看看 matrix[1][3] 就知道了

二、图的相关概念

最后，我们再明确一个图论中特有的度（degree）的概念，在无向图中，「度」就是每个节点相连的边的条数。

由于有向图的边有方向，所以有向图中每个节点「度」被细分为入度（indegree）和出度（outdegree），比如下图

img

其中节点 3 的入度为 3（有三条边指向它），出度为 1（它有 1 条边指向别的节点）。

三、图的分类

有向图，无向图，有向加权图，无向加权图。

有向加权图怎么表示

使用邻接表、我们不仅仅存储某个节点 x 的所有邻居节点，还存储 x 到每个邻居的权重，就实现了加权有向图

使用邻接矩阵我们矩阵中存储权值即可。

什么是无向图，无向图就是双向图。

四、图的遍历

数据结构被发明出来很多时候都是为了遍历和访问。所以遍历是所有数据结构的基础。

图应该如何遍历，可以参考下多叉树的遍历。

def traverse(root):
    if root is None:
        return
    # 前序位置
    for child in root.children:
        traverse(child)

但是多叉树和图最大的区别就是，图中可能是包含环的，从图中的某一个节点开始遍历，有可能走了一圈又回到该节点，所以我们应该使用一个visited数组进行辅助，这个visited数组可以避免我们走回头路。

visited = []
on_path = []
def traver(graph, s):
    if visited[s]:
        return
    visited[s] = True
    on_path[s] = True
    for neighbor in graph.neighbors(s):
        traverse(graph, neighbor)
    on_path[s] = False
        

我们可以粗略的理解为visited 数组为灰色的节点，on_path数组相当于绿色的数组。

在 visited 中被标记为 true 的节点用灰色表示，在 onPath 中被标记为 true 的节点用绿色表示，类比贪吃蛇游戏，visited 记录蛇经过过的格子，而 onPath 仅仅记录蛇身。在图的遍历过程中，onPath 用于判断是否成环，类比当贪吃蛇自己咬到自己（成环）的场景，这下你可以理解它们二者的区别了吧。

图的遍历和回溯算法区别为，：回溯算法关注的不是节点，而是树枝

# DFS 算法，关注点在节点
def traverse(root: TreeNode):
    if root is None:
        return
    print("进入节点", root)
    for child in root.children:
        traverse(child)
    print("离开节点", root)

# 回溯算法，关注点在树枝
def backtrack(root: TreeNode):
    if root is None:
        return
    for child in root.children:
        # 做选择
        print("从", root, "到", child)
        backtrack(child)
        # 撤销选择
        print("从", child, "到", root)

如果执行这段代码，你会发现根节点被漏掉了：

def traverse(root):
    if root is None:
        return
    for child in root.children:
        print("进入节点 {}".format(child))
        traverse(child)
        print("离开节点 {}".format(child))

所以对于这里「图」的遍历，我们应该用 DFS 算法，即把 onPath 的操作放到 for 循环外面，否则会漏掉记录起始点的遍历。

五、题目实践——797. 所有可能的路径

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

graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。

示例 1：

img

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

示例 2：

img

输入：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]]

提示：

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

思路：

这里只需要遍历一遍图即可知道答案，那么我们遍历图需要哪些条件呢

• 邻接表
• 开始节点

我们只需要这两个数据就可以了，那么我们遍历图需要两个数组第一个visited,第二个onpath,这两个数据是干嘛的。

visited是为了避免走回头路，避免图中有环走入死循环，onpath是为了记录图中的数据，题目中已经说了没有环，所以我们就不再需要visited数组了。

from typing import List


class Solution:

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        path = []
        result = []
        self.traverse(graph, 0, path, result)
        return result

    def traverse(self, graph: List[List[int]], s: int, path: List[int], result):
        path.append(s)

        if s == len(graph) - 1:
            result.append(path[:])

        for v in graph[s]:
            self.traverse(graph, v, path, result)
        path.pop()

但是这个代码还是有坑的，我们一般写递归条件需要return

但是我们发现这里没有return，为什么没有return呢？是因为我们一旦return,就会把前面path.append(s)这里的值进行重复添加。所以当我们需要return时需要这么写

from typing import List


class Solution:

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        path = []
        result = []
        self.traverse(graph, 0, path, result)
        return result

    def traverse(self, graph: List[List[int]], s: int, path: List[int], result):
        path.append(s)

        if s == len(graph) - 1:
            result.append(path[:])
            path.pop()
            return

        for v in graph[s]:
            self.traverse(graph, v, path, result)
        path.pop()

但是这里和我们代码随想录中写的还不一样，代码随想录中path的处理是在for循环中的，这里是在for循环外的，这里我们先要分清在for里面和外面的区别，里面是对路径进行回溯，外面是对节点进行回溯。

如果写在里面会少个根节点。那么我们可以为了维持我们之前的习惯，还是选择写在里面

from typing import List


class Solution:

    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        path = [0]
        result = []
        self.traverse(graph, 0, path, result)
        return result

    def traverse(self, graph: List[List[int]], s: int, path: List[int], result):
        if s == len(graph) - 1:
            result.append(path[:])
            return

        for v in graph[s]:
            path.append(v)
            self.traverse(graph, v, path, result)
            path.pop()