在蓝桥杯竞赛中，常见的图存储方式包括邻接矩阵、邻接表、链式前向星等。这些存储方式在不同的场景下有着各自的优势和适用性。
邻接矩阵
邻接矩阵是最常见的图的表示方法之一。对于一个有$n$个顶点的图，可以用一个$n \times n$的二维数组来表示。如果图中存在从顶点$i$到顶点$j$的边，则$adj[i][j]$为1，否则为0。邻接矩阵适用于稠密图，但在稀疏图中会占用较多的空间。
例题： 判断图中是否存在从顶点1到顶点3的边。
# 定义邻接矩阵
adj_matrix = [[0, 1, 0, 0],[0, 0, 1, 0],[0, 0, 0, 1],[0, 0, 0, 0]
]if adj_matrix[1][3] == 1:print("顶点1到顶点3存在边")
else:print("顶点1到顶点3不存在边")加边
def add_edge(adj_matrix, u, v):adj_matrix[u][v] = 1adj_matrix[v][u] = 1 # 如果是有向图则不需要这行邻接表
邻接表是一种更节省空间的表示方法，它用一个数组和若干个链表来表示图。数组的每个元素表示一个顶点，对应的链表存储了从该顶点出发的所有边。邻接表适用于稀疏图，空间复杂度较低。
例题： 判断图中是否存在从顶点1到顶点3的边。
# 定义邻接表
adj_list = {1: [2],2: [3],3: []
}if 3 in adj_list[1]:print("顶点1到顶点3存在边")
else:print("顶点1到顶点3不存在边")加边：
def add_edge(adj_list, u, v):if u not in adj_list:adj_list[u] = []adj_list[u].append(v)# 如果是有向图，则不需要下面这行if v not in adj_list:adj_list[v] = []adj_list[v].append(u)链式前向星
链式前向星是一种用于存储稀疏图的高效表示方法，它通过三个数组来表示图的结构：head、nxt、to。其中head[u]存储了顶点$u$的第一条边的编号，nxt[i]存储了编号为$i$的边的下一条边的编号，to[i]存储了编号为$i$的边的终点。
例题： 使用链式前向星存储图，并遍历顶点1的所有邻居。
class Edge:def __init__(self, to, weight):self.to = toself.weight = weightself.next = Nonedef add(u, v, weight):global cntcnt += 1nxt[cnt] = head[u]head[u] = cntto[cnt] = v# 初始化
n = 4
head = [-1] * n
nxt = [0] * n
to = [0] * n
cnt = -1# 添加边
add(1, 2, 5)
add(1, 3, 3)
add(2, 3, 2)
add(2, 4, 6)
add(3, 4, 7)# 遍历顶点1的所有邻居
i = head[1]
while i != -1:print("顶点1的邻居:", to[i])i = nxt[i]关于链式前向星的详细讲解：（参考这篇博客链式前向星）
以下是对原文的Python讲解：
以下是对原文的Python讲解：前向星是一种特殊的边集数组，我们按照起点从小到大排序，如果起点相同就按照终点从小到大排序，并记录下以某个点为起点的所有边在数组中的起始位置和存储长度，那么前向星就构造好了。用`len[i]`来记录所有以i为起点的边在数组中的存储长度。用`head[i]`记录以i为边集在数组中的第一个存储位置。举个例子：我们输入边的顺序为：1 2
2 3
3 4
1 3
4 1
1 5
4 5
那么排完序后就得到：
编号: 1 2 3 4 5 6 7
起点u: 1 1 1 2 3 4 4
终点v: 2 3 5 3 4 1 5
得到：
head[1] = 1 len[1] = 3
head[2] = 4 len[2] = 1
head[3] = 5 len[3] = 1
head[4] = 6 len[4] = 2
但是利用前向星会有排序操作，如果用快排时间至少为O(nlog(n))。 如果用链式前向星，就可以避免排序。 我们建立边结构体为：
```python
class Edge:def __init__(self, to, w):self.next = Noneself.to = toself.w = w初始化cnt = 0，这样，现在我们还是按照上面的图和输入来模拟一下：
# 初始化
cnt = 0
edge = [Edge(0, 0) for _ in range(7)]
head = [-1] * 6# 加边
add(1, 2, 0)
add(2, 3, 0)
add(3, 4, 0)
add(1, 3, 0)
add(4, 1, 0)
add(1, 5, 0)
add(4, 5, 0)很明显，head[i]保存的是以i为起点的所有边中编号最大的那个，而把这个当作顶点i的第一条起始边的位置。
这样在遍历时是倒着遍历的，也就是说与输入顺序是相反的，不过这样不影响结果的正确性。
比如以上图为例，以节点1为起点的边有3条，它们的编号分别是0, 3, 5，而head[1] = 5。
我们在遍历以u节点为起始位置的所有边的时候是这样的：
u = 1
i = head[u]
while i != -1:print("起点为{}的边的终点是{}，权重为{}".format(u, edge[i].to, edge[i].w))i = edge[i].next这样就可以正确地遍历出以节点1为起始位置的所有边。
以上是在Python中常见的图存储方式及其应用例题。在蓝桥杯竞赛中，图相关的题目往往涉及到图的存储、遍历、最短路径、最小生成树等基本算法和数据结构。掌握这些常见的图存储方式对于解决相关问题非常重要。
