在蓝桥杯竞赛中，常见的图存储方式包括邻接矩阵、邻接表、链式前向星等。这些存储方式在不同的场景下有着各自的优势和适用性。
邻接矩阵
邻接矩阵是最常见的图的表示方法之一。对于一个有$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] = 1
adj_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 = to
self.weight = weight
self.next = None
def add(u, v, weight):
global cnt
cnt += 1
nxt[cnt] = head[u]
head[u] = cnt
to[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]
关于链式前向星的详细讲解：（参考这篇博客https://blog.csdn.net/Binary_Heap/article/details/78209086）
点击查看代码
以下是对原文的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 = None
self.to = to
self.w = w
另外还有一个数组head[]，它是用来表示以i为起点的第一条边存储的位置，实际上你会发现这里的第一条边存储的位置其实在以i为起点的所有边的最后输入的那个编号。
head[]数组一般初始化为-1，对于加边的add函数是这样的：
def add(u, v, w):
global cnt
edge[cnt].w = w
edge[cnt].to = v
edge[cnt].next = head[u]
head[u] = cnt
cnt += 1
初始化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为起始位置的所有边。
</details>
以上是在Python中常见的图存储方式及其应用例题。在蓝桥杯竞赛中，图相关的题目往往涉及到图的存储、遍历、最短路径、最小生成树等基本算法和数据结构。掌握这些常见的图存储方式对于解决相关问题非常重要。