数据结构——BFS广度优先遍历之图的最短路径
主要思想：
1.采用邻接表存储图结构
2.求最短路径 采用队列存储BFS遍历结果
3.首先入队 第一个结点，再遍历所有与第一个结点相连的所有结点并入队，与此同时，更新当前点到其他点的路径长度
变量说明：
1.用来表达邻接表的数组
h[n*2] 存放图的所有结点
e[idx] 当前结点的值
nxt[idx] 存放当前结点的下一个结点索引
2.q 表示队列
dis 存储距离
核心代码：
# a b 之间存在边 idx = 0 def add(a,b): e[idx] = b nxt[idx] = h[a] h[a] = idx idx += 1 # 广度优先遍历 def bfs(): q = [] q.append(1) dis[1] = 0 # 表示第一个结点当前距离为 0 while len(q): # 结点出队 t = q[0] q.pop(0) # 获取与当前结点相连接的结点 i = h[t] while i != -1: j = e[i] if dis[j]== -1： dis[j] = dis[t]+1 # 将相邻结点入队 q.append(j) i = nxt[i]
完整代码：
def main():
global h,e,nxt,idx,dis
n = int(input("请输入n："))
m = int(input("请输入m："))
h = [-1]*n*2
e = [-1]*n*2
nxt = [-1]*n*2
dis = [-1]*n*2 # 距离数组 索引为点标号
idx = 0
for i in range(m):
a = int(input("请输入a："))
b = int(input("请输入b："))
add(a,b)
bfs()
print(dis[n])
def add(a,b):
global idx
e[idx] = b
nxt[idx] = h[a]
h[a] = idx
idx += 1
def bfs():
dis[1] = 0
q = [] # 队列
q.append(1)
while len(q):
t = q[0]
print(q)
q.pop(0)
i = h[t]
while i != -1:
if dis[e[i]] == -1:
dis[e[i]] = dis[t]+1
q.append(e[i])
i = nxt[i]
if __name__ == '__main__':
main() 
