图

1. 图的存储
邻接表 把每个顶点可以到达的顶点存储成一个列表，每个列表存储到一个列表中，为邻接表
邻接矩阵 定义一个二维数组，下标为顶点，如果点和点之间有边，就把对应位置设置为1

# 顶点为[0, n]，邻接表
vec = [
    [1, 2, 3],  # 顶点0和顶点1、2、3之间有边
    [2, 3, 4],  # 顶点1和顶点2、3、4之间有边
    [4, 5, 6]   # 顶点2和顶点4、5、6之间有边
    [],
    [5, 6]
]

# 邻接矩阵
vec = [[0 for i in range(n)] for i in range(n)]
#### vec = [[0] * n] * n 会浅拷贝数组
# [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
# 顶点间有边则记为1或权重
# 有向图只记录一个
# 无向图记录两个
vec[0][1] = 1
vec[1][0] = 1

2. 图的遍历
深度优先搜索 (DFS)
遇见点就扎访问，选取一个顶点可以到达的点访问，不行再回来重选，可以求连通分量
1.邻接矩阵版

# n个顶点
# G为邻接矩阵
def DFS(u, depth): # 访问顶点u
    vis[u] = True   # 已经访问过顶点u
    for v in range(n):  # 对于u能到达的顶点且未被访问过的顶点v，访问
        if vis[v] == False and G[u][v] != 0:
            DFS(v, depth + 1)

vis = [False] * n       # 记录这个顶点是否访问过
count = 0
for u in range(n): # 对于每一个顶点，都去访问下
    if vis[u] == False: # 每进入一次都是一个连通分量
        count += 1 
        DFS(u, 1)

2. 邻接表版

# n个顶点
# G为邻接表
def DFS(u, depth): # 访问顶点u
    vis[u] = True   # 已经访问过顶点u
    for v in G[u]:  # 对于u能到达的顶点且未被访问过的顶点v，访问
        if vis[v] == False:
            DFS(v, depth + 1)

vis = [False] * n       # 记录这个顶点是否访问过
count = 0
for u in range(n): # 对于每一个顶点，都去访问下
    if vis[u] == False: # 每进入一次都是一个连通分量
        count += 1 
        DFS(u, 1)

广度优先搜索 (BFS)
访问顶点时，把该顶点可以去的顶点先放到队列中，按队列中的顶点进行访问，可以求最短路径
1.邻接矩阵版

# n个顶点
# G为邻接矩阵


from collections import deque


def BFS(u): # 访问顶点u
    dq = deque()
    dq.appendleft(u)    # 进入队列中
    vis[u] = True
    while len(dq) != 0: # 如果队列为空，就不再访问
        u = dq.pop() # 出队列
        for v in range(n):  # 对于u能到达的顶点且未被访问过的顶点v，访问
            if vis[v] == False and G[u][v] != 0:
                dq.appendleft(v)
                vis[v] = True

vis = [False] * n       # 记录这个顶点是否访问过
count = 0
for u in range(n): # 对于每一个顶点，都去访问下
    if vis[u] == False: # 每进入一次都是一个连通分量
        count += 1 
        BFS(u)

2. 邻接表版

# n个顶点
# G为邻接表
from collections import deque

def BFS(u): # 访问顶点u
    dq = deque()
    dq.appendleft(u)    # 进入队列中
    vis[u] = True
    while len(dq) != 0: # 如果队列为空，就不再访问
        u = dq.pop() # 出队列
        for v in G[u]:  # 对于u能到达的顶点且未被访问过的顶点v，访问
            if vis[v] == False:
                dq.appendleft(v)
                vis[v] = True

vis = [False] * n       # 记录这个顶点是否访问过
count = 0
for u in range(n): # 对于每一个顶点，都去访问下
    if vis[u] == False: # 每进入一次都是一个连通分量
        count += 1 
        BFS(u)

3. 图的连通分量
并查集
深度优先搜索（DFS）

4. 图中的最短路径
Floyd算法 求任意两点间的最短路径
BF算法 SPFA 可以求带负权的图
Dijkstra算法 单源最短路径

5. 最小生成树
6. 有向无环图
7. 拓扑排序
8. 网络流