第5章图上机练习答案

应用离散数学图PAGE杭电－周丽、方景龙第五章PAGE3第5章图上机练习编写下列程序并计算至少1个算例编程使得程序可以接受一个图的点边作为输入，然后显示出这个图。程序代码importnetworkxasnximportmatplotlib.pyplotaspltdefdraw_graph(nodes,edges,directed=False,title="图结构可视化",save_path=None):"""接受顶点和边作为输入，绘制并显示图参数说明：nodes:可迭代对象，图的顶点集合，支持数字、字符串等类型，如[1,2,3]或['A','B','C']edges:列表，每个元素为二元组(u,v)表示一条边；有向图中u为起点，v为终点directed:布尔值，是否为有向图，默认False（无向图）title:字符串，可视化窗口的标题save_path:可选字符串，若传入则将图片保存到该路径，如'graph.png'"""#1.创建图对象ifdirected:G=nx.DiGraph()#有向图else:G=nx.Graph()#无向图#2.添加顶点和边G.add_nodes_from(nodes)G.add_edges_from(edges)#3.设置布局：固定随机种子的力导向布局，每次运行位置一致pos=nx.spring_layout(G,seed=42)#4.绘制配置plt.figure(figsize=(8,6))plt.title(title,fontsize=14,pad=15)#绘制节点nx.draw_networkx_nodes(G,pos,node_size=800,node_color="#4A90E2",edgecolors="white",linewidths=2)#绘制边（有向图显示箭头）nx.draw_networkx_edges(G,pos,width=2,edge_color="#555555",arrowstyle="->",arrowsize=22ifdirectedelse0)#绘制顶点标签nx.draw_networkx_labels(G,pos,font_size=12,font_color="white",font_weight="bold")#隐藏坐标轴plt.axis("off")plt.tight_layout()#保存图片（可选）ifsave_path:plt.savefig(save_path,dpi=300,bbox_inches="tight")#弹出窗口显示plt.show()#==========测试算例与运行入口==========if__name__=="__main__":#测试1：无向简单图print("测试1：绘制5顶点无向简单图")nodes_1=[1,2,3,4,5]edges_1=[(1,2),(1,3),(2,3),(2,4),(3,5),(4,5)]draw_graph(nodes_1,edges_1,directed=False,title="无向简单图（5个顶点）")#测试2：有向图print("测试2：绘制有向图")nodes_2=["A","B","C","D","E"]edges_2=[("A","B"),("A","C"),("B","D"),("C","D"),("D","E"),("E","A")]draw_graph(nodes_2,edges_2,directed=True,title="有向图示例")#测试3：经典图论结构——彼得森图print("测试3：绘制彼得森图（图论经典结构）")nodes_3=list(range(10))edges_3=[(0,1),(1,2),(2,3),(3,4),(4,0),#外层五边形(0,5),(1,6),(2,7),(3,8),(4,9),#辐条边(5,7),(7,9),(9,6),(6,8),(8,5)#内层五角星]draw_graph(nodes_3,edges_3,directed=False,title="彼得森图（10顶点经典图）")算例测试测试1窗口：显示5个顶点、6条边的无向简单图，顶点编号1~5，结构清晰呈现。测试2窗口：显示带箭头的有向图，箭头方向对应边的起点到终点。测试3窗口：显示标准的彼得森图结构，验证经典图论模型。给定一个图的邻接矩阵，编程求它的连通矩阵并判断它是否连通，若不连通，求出连通分图个数。程序代码defwarshall(adj_matrix):"""Warshall算法计算传递闭包（正闭包：长度≥1的路径可达性）参数：adj_matrix-图的邻接矩阵（二维列表，元素为0/1）返回：长度≥1的可达矩阵"""n=len(adj_matrix)reach=[row.copy()forrowinadj_matrix]forkinrange(n):foriinrange(n):forjinrange(n):reach[i][j]=reach[i][j]or(reach[i][k]andreach[k][j])returnreachdefget_connectivity_matrix(adj_matrix):"""生成图的连通矩阵（自反传递闭包：自身到自身视为连通）返回：完整连通矩阵"""n=len(adj_matrix)reach=warshall(adj_matrix)#对角线置1：顶点自身与自身连通（平凡路径）foriinrange(n):reach[i][i]=1returnreachdefis_connected(connectivity_matrix):"""判断图是否连通：连通矩阵所有元素均为1则连通"""forrowinconnectivity_matrix:if0inrow:returnFalsereturnTruedefcount_connected_components(connectivity_matrix):"""计算连通分图（连通分支）的个数基于可达性等价类染色统计"""n=len(connectivity_matrix)visited=[False]*ncount=0foriinrange(n):ifnotvisited[i]:count+=1#将与i连通的所有顶点标记为已访问forjinrange(n):ifconnectivity_matrix[i][j]==1:visited[j]=Truereturncountdefprint_matrix(matrix,name):"""格式化输出矩阵"""print(f"{name}：")forrowinmatrix:print("",row)print()#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,adj_matrix):print(f"====={test_name}=====")print_matrix(adj_matrix,"输入邻接矩阵")conn_matrix=get_connectivity_matrix(adj_matrix)print_matrix(conn_matrix,"连通矩阵")connected=is_connected(conn_matrix)print(f"是否连通：{'是'ifconnectedelse'否'}")ifnotconnected:comp_num=count_connected_components(conn_matrix)print(f"连通分图个数：{comp_num}")print("-"*40)print()#测试1：3顶点连通无向链（0-1-2）adj1=[[0,1,0],[1,0,1],[0,1,0]]run_test("测试1：3顶点连通无向链",adj1)#测试2：4顶点非连通图（两个分支：{0,1},{2,3}）adj2=[[0,1,0,0],[1,0,0,0],[0,0,0,1],[0,0,1,0]]run_test("测试2：4顶点双分支非连通图",adj2)#测试3：5顶点三分支图（0孤立，1-2连通，3-4连通）adj3=[[0,0,0,0,0],[0,0,1,0,0],[0,1,0,0,0],[0,0,0,0,1],[0,0,0,1,0]]run_test("测试3：5顶点三分支非连通图",adj3)#测试4：4顶点完全图K4adj4=[[0,1,1,1],[1,0,1,1],[1,1,0,1],[1,1,1,0]]run_test("测试4：4顶点完全图K4",adj4)算例测试=====测试1：3顶点连通无向链=====输入邻接矩阵：[0,1,0][1,0,1][0,1,0]连通矩阵：[1,1,1][1,1,1][1,1,1]是否连通：是=====测试2：4顶点双分支非连通图=====输入邻接矩阵：[0,1,0,0][1,0,0,0][0,0,0,1][0,0,1,0]连通矩阵：[1,1,0,0][1,1,0,0][0,0,1,1][0,0,1,1]是否连通：否连通分图个数：2=====测试3：5顶点三分支非连通图=====输入邻接矩阵：[0,0,0,0,0][0,0,1,0,0][0,1,0,0,0][0,0,0,0,1][0,0,0,1,0]连通矩阵：[1,0,0,0,0][0,1,1,0,0][0,1,1,0,0][0,0,0,1,1][0,0,0,1,1]是否连通：否连通分图个数：3=====测试4：4顶点完全图K4=====输入邻接矩阵：[0,1,1,1][1,0,1,1][1,1,0,1][1,1,1,0]连通矩阵：[1,1,1,1][1,1,1,1][1,1,1,1][1,1,1,1]是否连通：是编程判断一个图中是否是欧拉图。（1）程序代码fromcollectionsimportdequedefis_connected_undirected(adj_matrix):"""判断无向图是否连通（支持多重图，边数>0即视为有边）"""n=len(adj_matrix)ifn<=1:returnTrue#单个顶点/空图视为连通visited=[False]*nq=deque([0])visited[0]=Truewhileq:u=q.popleft()forvinrange(n):ifadj_matrix[u][v]>0andnotvisited[v]:visited[v]=Trueq.append(v)returnall(visited)defget_degrees_undirected(adj_matrix):"""计算无向图每个顶点的度数（支持多重边）"""return[sum(row)forrowinadj_matrix]defcheck_euler_graph(adj_matrix):"""判断无向图是否为欧拉图/半欧拉图返回：(类型,详细说明)类型：euler=欧拉图,semi_euler=半欧拉图,none=非欧拉图"""n=len(adj_matrix)ifn==0:return"none","空图无意义"#步骤1：判断连通性connected=is_connected_undirected(adj_matrix)ifnotconnected:return"none","图不连通，不存在欧拉回路/欧拉路径"#步骤2：统计度数与奇度顶点degrees=get_degrees_undirected(adj_matrix)odd_vertices=[idxforidx,dinenumerate(degrees)ifd%2!=0]odd_count=len(odd_vertices)#步骤3：按规则判定ifodd_count==0:return"euler",(f"所有顶点度数均为偶数，且图连通，是欧拉图（存在欧拉回路）。\n"f"各顶点度数：{degrees}")elifodd_count==2:return"semi_euler",(f"恰好2个奇度顶点（顶点{odd_vertices[0]}、顶点{odd_vertices[1]}），且图连通，是半欧拉图。\n"f"存在欧拉路径，起点和终点为两个奇度顶点。\n"f"各顶点度数：{degrees}")else:return"none",(f"奇度顶点共{odd_count}个，不符合欧拉图/半欧拉图条件。\n"f"奇度顶点列表：{odd_vertices}\n"f"各顶点度数：{degrees}")#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,adj_matrix):print(f"====={test_name}=====")print("邻接矩阵：")forrowinadj_matrix:print(f"{row}")typ,msg=check_euler_graph(adj_matrix)print(f"判定结果：",end="")iftyp=="euler":print("✅欧拉图")eliftyp=="semi_euler":print("⚠️半欧拉图")else:print("❌非欧拉图")print(f"详细说明：{msg}")print("-"*50)print()#测试1：3顶点环（三角形，简单图）——欧拉图adj1=[[0,1,1],[1,0,1],[1,1,0]]run_test("测试1：3顶点环（三角形）",adj1)#测试2：4顶点路径图——半欧拉图adj2=[[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]]run_test("测试2：4顶点路径图",adj2)#测试3：哥尼斯堡七桥（多重图）——非欧拉图#顶点0~3对应四块陆地，矩阵元素为桥的数量adj3=[[0,2,2,1],[2,0,0,1],[2,0,0,1],[1,1,1,0]]run_test("测试3：哥尼斯堡七桥图",adj3)#测试4：非连通图（两个不相连的三角形）——非欧拉图adj4=[[0,1,1,0,0,0],[1,0,1,0,0,0],[1,1,0,0,0,0],[0,0,0,0,1,1],[0,0,0,1,0,1],[0,0,0,1,1,0]]run_test("测试4：非连通双三角形",adj4)#测试5：单个顶点（平凡图）——欧拉图adj5=[[0]]run_test("测试5：单顶点平凡图",adj5)（2）算例测试=====测试1：3顶点环（三角形）=====邻接矩阵：[0,1,1][1,0,1][1,1,0]判定结果：✅欧拉图详细说明：所有顶点度数均为偶数，且图连通，是欧拉图（存在欧拉回路）。各顶点度数：[2,2,2]=====测试2：4顶点路径图=====邻接矩阵：[0,1,0,0][1,0,1,0][0,1,0,1][0,0,1,0]判定结果：⚠️半欧拉图详细说明：恰好2个奇度顶点（顶点0、顶点3），且图连通，是半欧拉图。存在欧拉路径，起点和终点为两个奇度顶点。各顶点度数：[1,2,2,1]=====测试3：哥尼斯堡七桥图=====邻接矩阵：[0,2,2,1][2,0,0,1][2,0,0,1][1,1,1,0]判定结果：❌非欧拉图详细说明：奇度顶点共4个，不符合欧拉图/半欧拉图条件。奇度顶点列表：[0,1,2,3]各顶点度数：[5,3,3,3]=====测试4：非连通双三角形=====邻接矩阵：[0,1,1,0,0,0][1,0,1,0,0,0][1,1,0,0,0,0][0,0,0,0,1,1][0,0,0,1,0,1][0,0,0,1,1,0]判定结果：❌非欧拉图详细说明：图不连通，不存在欧拉回路/欧拉路径=====测试5：单顶点平凡图=====邻接矩阵：[0]判定结果：✅欧拉图详细说明：所有顶点度数均为偶数，且图连通，是欧拉图（存在欧拉回路）。各顶点度数：[0]4．将弗罗莱算法实现为程序，在一个所有顶点的度数为偶数的连通图中寻求欧拉回路。（1）程序代码fromcollectionsimportdequedefbfs_reachable(adj,start,target):"""BFS判断无向图中start到target是否可达，adj[u][v]>0表示有边"""n=len(adj)visited=[False]*nq=deque([start])visited[start]=Truewhileq:u=q.popleft()ifu==target:returnTrueforvinrange(n):ifadj[u][v]>0andnotvisited[v]:visited[v]=Trueq.append(v)returnvisited[target]defis_bridge(adj,u,v):"""判断无向边(u,v)是否为桥（割边）：移除后两端点不再连通"""ifadj[u][v]==0:returnFalse#临时移除一条边adj[u][v]-=1adj[v][u]-=1#检查移除后u和v是否还连通reachable=bfs_reachable(adj,u,v)#恢复边adj[u][v]+=1adj[v][u]+=1returnnotreachabledeftotal_edges(adj):"""计算无向图的总边数（支持多重图）"""returnsum(sum(row)forrowinadj)//2defis_connected_and_euler(adj):"""验证图是否为无向欧拉图：连通+所有顶点度数为偶数"""n=len(adj)degrees=[sum(row)forrowinadj]#1.检查奇度顶点数odd_count=sum(1fordindegreesifd%2!=0)ifodd_count!=0:returnFalse,f"奇度顶点共{odd_count}个，不满足欧拉图条件"#2.检查所有非零度顶点连通start=next((iforiinrange(n)ifdegrees[i]>0),0)visited=[False]*nq=deque([start])visited[start]=Truewhileq:u=q.popleft()forvinrange(n):ifadj[u][v]>0andnotvisited[v]:visited[v]=Trueq.append(v)foriinrange(n):ifdegrees[i]>0andnotvisited[i]:returnFalse,"图不连通，不存在欧拉回路"returnTrue,"满足欧拉图条件"deffleury_euler_circuit(adj_matrix):"""弗罗莱算法求解无向欧拉图的欧拉回路参数：adj_matrix-无向图邻接矩阵（元素为边的重数，支持多重图）返回：欧拉回路顶点序列（列表）"""#前置校验is_euler,msg=is_connected_and_euler(adj_matrix)ifnotis_euler:raiseValueError(f"无法求解欧拉回路：{msg}")n=len(adj_matrix)adj=[row.copy()forrowinadj_matrix]#复制矩阵，不修改原输入#初始化：从第一个非零度顶点出发degrees=[sum(row)forrowinadj]current=next((iforiinrange(n)ifdegrees[i]>0),0)circuit=[current]edges_left=total_edges(adj)whileedges_left>0:#获取当前顶点的所有邻接点neighbors=[vforvinrange(n)ifadj[current][v]>0]#优先选择非桥边next_v=Noneforvinneighbors:ifnotis_bridge(adj,current,v):next_v=vbreak#若所有边都是桥，任选第一条ifnext_visNone:next_v=neighbors[0]#删除走过的边adj[current][next_v]-=1adj[next_v][current]-=1edges_left-=1#更新当前顶点，加入回路current=next_vcircuit.append(current)returncircuit#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,adj_matrix):print(f"====={test_name}=====")print("邻接矩阵：")forrowinadj_matrix:print(f"{row}")try:circuit=fleury_euler_circuit(adj_matrix)print(f"欧拉回路顶点序列：{circuit}")print(f"回路边数：{len(circuit)-1}，总边数验证：{total_edges(adj_matrix)}")print("✅求解成功")exceptValueErrorase:print(f"❌{e}")print("-"*50)print()#测试1：3顶点三角形（简单欧拉图）adj1=[[0,1,1],[1,0,1],[1,1,0]]run_test("测试1：3顶点三角形",adj1)#测试2：4顶点环（正方形）adj2=[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]run_test("测试2：4顶点环",adj2)#测试3：两个三角形共享顶点0（5顶点欧拉图）adj3=[[0,1,1,1,1],[1,0,1,0,0],[1,1,0,0,0],[1,0,0,0,1],[1,0,0,1,0]]run_test("测试3：双三角形共顶点",adj3)#测试4：2顶点多重边（多重图欧拉图）adj4=[[0,2],[2,0]]run_test("测试4：2顶点双重边（多重图）",adj4)#测试5：非欧拉图反例（4顶点路径，2个奇度顶点）adj5=[[0,1,0,0],[1,0,1,0],[0,1,0,1],[0,0,1,0]]run_test("测试5：4顶点路径（非欧拉图）",adj5)（2）算例测试=====测试1：3顶点三角形=====邻接矩阵：[0,1,1][1,0,1][1,1,0]欧拉回路顶点序列：[0,1,2,0]回路边数：3，总边数验证：3✅求解成功=====测试2：4顶点环=====邻接矩阵：[0,1,0,1][1,0,1,0][0,1,0,1][1,0,1,0]欧拉回路顶点序列：[0,1,2,3,0]回路边数：4，总边数验证：4✅求解成功=====测试3：双三角形共顶点=====邻接矩阵：[0,1,1,1,1][1,0,1,0,0][1,1,0,0,0][1,0,0,0,1][1,0,0,1,0]欧拉回路顶点序列：[0,1,2,0,3,4,0]回路边数：6，总边数验证：6✅求解成功=====测试4：2顶点双重边（多重图）=====邻接矩阵：[0,2][2,0]欧拉回路顶点序列：[0,1,0]回路边数：2，总边数验证：2✅求解成功=====测试5：4顶点路径（非欧拉图）=====邻接矩阵：[0,1,0,0][1,0,1,0][0,1,0,1][0,0,1,0]❌无法求解欧拉回路：奇度顶点共2个，不满足欧拉图条件5．编程检查指定的回路是否是一个哈密顿回路。（1）程序代码defis_hamiltonian_circuit(adj_matrix,circuit):"""检查指定回路是否为无向图的哈密顿回路参数：adj_matrix:无向图邻接矩阵，元素为对应边的重数（简单图为0/1）circuit:待检查的回路顶点列表，如[0,1,2,0]返回：(是否为哈密顿回路,说明信息)"""n=len(adj_matrix)#1.空图边界处理ifn==0:returnFalse,"空图不存在哈密顿回路"#2.检查回路顶点编号合法性forvincircuit:ifv<0orv>=n:returnFalse,f"回路包含非法顶点{v}，超出图的顶点范围（0~{n-1}）"#3.检查回路闭合性：首尾顶点必须相同ifcircuit[0]!=circuit[-1]:returnFalse,"回路不闭合，首尾顶点不一致，不属于回路"#4.检查回路长度：n个顶点的哈密顿回路应有n+1个顶点（含重复的起点）expected_len=n+1iflen(circuit)!=expected_len:returnFalse,f"回路长度为{len(circuit)}，合法哈密顿回路长度应为{expected_len}"#5.检查顶点唯一性与覆盖性：除起点终点外，所有顶点恰好出现一次inner_vertices=circuit[:-1]iflen(set(inner_vertices))!=n:returnFalse,"回路存在重复顶点（起点终点除外），或未覆盖图中全部顶点"#6.统计回路中每条无向边的使用次数edge_usage={}foriinrange(len(circuit)-1):u,v=circuit[i],circuit[i+1]#无向边统一为有序元组，消除方向差异edge=tuple(sorted((u,v)))edge_usage[edge]=edge_usage.get(edge,0)+1#7.检查边的使用次数是否不超过图中边的重数for(u,v),usedinedge_usage.items():available=adj_matrix[u][v]ifused>available:returnFalse,f"边({u},{v})在回路中使用了{used}次，但图中仅有{available}条，超出边数限制"#所有条件满足returnTrue,"满足哈密顿回路定义：闭合、经过所有顶点恰好一次、边使用合法"#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(test_name,adj_matrix,circuit):print(f"====={test_name}=====")print(f"待检查回路：{circuit}")is_ham,msg=is_hamiltonian_circuit(adj_matrix,circuit)print(f"判定结果：{'✅是哈密顿回路'ifis_hamelse'❌不是哈密顿回路'}")print(f"说明：{msg}")print("-"*55)print()#测试1：3顶点三角形（简单图），正确哈密顿回路adj1=[[0,1,1],[1,0,1],[1,1,0]]run_test("测试1：3顶点三角形-合法回路",adj1,[0,1,2,0])#测试2：回路不闭合（路径而非回路）run_test("测试2：不闭合路径",adj1,[0,1,2])#测试3：顶点重复，未覆盖全部顶点run_test("测试3：顶点重复且未全覆盖",adj1,[0,1,0,2,0])#测试4：4顶点环（正方形），合法哈密顿回路adj4=[[0,1,0,1],[1,0,1,0],[0,1,0,1],[1,0,1,0]]run_test("测试4：4顶点环-合法回路",adj4,[0,1,2,3,0])#测试5：回路包含不存在的边run_test("测试5：含不存在的边",adj4,[0,2,1,3,0])#测试6：2顶点多重图（两条边），合法哈密顿回路adj6=[[0,2],[2,0]]run_test("测试6：2顶点双重边-合法回路",adj6,[0,1,0])#测试7：2顶点简单图（一条边），非法（边重复使用）adj7=[[0,1],[1,0]]run_test("测试7：2顶点单边-边重复",adj7,[0,1,0])#测试8：5顶点完全图K5，合法哈密顿回路adj8=[[0,1,1,1,1],[1,0,1,1,1],[1,1,0,1,1],[1,1,1,0,1],[1,1,1,1,0]]run_test("测试8：5顶点完全图-合法回路",adj8,[0,2,4,1,3,0])（2）算例测试=====测试1：3顶点三角形-合法回路=====待检查回路：[0,1,2,0]判定结果：✅是哈密顿回路说明：满足哈密顿回路定义：闭合、经过所有顶点恰好一次、边使用合法=====测试2：不闭合路径=====待检查回路：[0,1,2]判定结果：❌不是哈密顿回路说明：回路不闭合，首尾顶点不一致，不属于回路=====测试3：顶点重复且未全覆盖=====待检查回路：[0,1,0,2,0]判定结果：❌不是哈密顿回路说明：回路长度为5，合法哈密顿回路长度应为4=====测试4：4顶点环-合法回路=====待检查回路：[0,1,2,3,0]判定结果：✅是哈密顿回路说明：满足哈密顿回路定义：闭合、经过所有顶点恰好一次、边使用合法=====测试5：含不存在的边=====待检查回路：[0,2,1,3,0]判定结果：❌不是哈密顿回路说明：边(0,2)在回路中使用了1次，但图中仅有0条，超出边数限制=====测试6：2顶点双重边-合法回路=====待检查回路：[0,1,0]判定结果：✅是哈密顿回路说明：满足哈密顿回路定义：闭合、经过所有顶点恰好一次、边使用合法=====测试7：2顶点单边-边重复=====待检查回路：[0,1,0]判定结果：❌不是哈密顿回路说明：边(0,1)在回路中使用了2次，但图中仅有1条，超出边数限制=====测试8：5顶点完全图-合法回路=====待检查回路：[0,2,4,1,3,0]判定结果：✅是哈密顿回路说明：满足哈密顿回路定义：闭合、经过所有顶点恰好一次、边使用合法6．将广度优先搜索算法实现为程序，在连通简单图中，求两个顶点之间的最短路。（1）程序代码fromcollectionsimportdequedefbfs_shortest_path(adj_matrix,start,end):"""用广度优先搜索求解连通简单图中两顶点间的最短路径参数:adj_matrix:list[list[int]]，无向简单图的邻接矩阵，元素为0或1start:int，起点顶点编号end:int，终点顶点编号返回:tuple:(最短路径顶点列表,路径长度（边数）)若两顶点不连通则返回(None,-1)"""vertex_count=len(adj_matrix)#1.校验顶点编号合法性ifstart<0orstart>=vertex_countorend<0orend>=vertex_count:raiseValueError(f"顶点编号超出范围，有效编号为0~{vertex_count-1}")#2.起点与终点重合的特殊情况ifstart==end:return[start],0#3.初始化辅助数组与队列visited=[False]*vertex_count#标记顶点是否已被访问prev=[-1]*vertex_count#prev[v]表示到达顶点v的前一个顶点queue=deque()#起点入队，标记为已访问queue.append(start)visited[start]=True#4.BFS主循环whilequeue:current=queue.popleft()#遍历当前顶点的所有邻接点forneighborinrange(vertex_count):ifadj_matrix[current][neighbor]==1andnotvisited[neighbor]:visited[neighbor]=Trueprev[neighbor]=current#找到终点，回溯构造路径ifneighbor==end:path=[]node=endwhilenode!=-1:path.append(node)node=prev[node]path.reverse()#反转得到从起点到终点的正向路径returnpath,len(path)-1#未找到终点，邻接点入队继续扩展queue.append(neighbor)#5.遍历完成仍未到达终点（图不连通）returnNone,-1#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(case_name,adj_matrix,start,end):print(f"====={case_name}=====")print(f"起点：{start}，终点：{end}")try:path,length=bfs_shortest_path(adj_matrix,start,end)ifpathisnotNone:print(f"最短路径：{path}")print(f"路径长度（边数）：{length}")else:print("两顶点不连通，不存在路径")exceptValueErrorase:print(f"输入错误：{e}")print("-"*50)print()#测试图1：5顶点连通简单图#结构：0-1,0-2,1-3,2-3,3-4adj_5v=[[0,1,1,0,0],[1,0,0,1,0],[1,0,0,1,0],[0,1,1,0,1],[0,0,0,1,0]]run_test("测试1：直接相邻的顶点（0→1）",adj_5v,0,1)run_test("测试2：单次中转的路径（0→3）",adj_5v,0,3)run_test("测试3：多次中转的路径（0→4）",adj_5v,0,4)run_test("测试4：起点与终点重合（2→2）",adj_5v,2,2)run_test("测试5：反向查询路径（4→0）",adj_5v,4,0)#测试图2：6顶点连通图（验证多分支场景）#结构：0连接1/2,1连接3,2连接3/4,3连接5,4连接5adj_6v=[[0,1,1,0,0,0],[1,0,0,1,0,0],[1,0,0,1,1,0],[0,1,1,0,0,1],[0,0,1,0,0,1],[0,0,0,1,1,0]]run_test("测试6：6顶点图多分支最短路径（0→5）",adj_6v,0,5)（2）算例测试=====测试1：直接相邻的顶点（0→1）=====起点：0，终点：1最短路径：[0,1]路径长度（边数）：1=====测试2：单次中转的路径（0→3）=====起点：0，终点：3最短路径：[0,1,3]路径长度（边数）：2=====测试3：多次中转的路径（0→4）=====起点：0，终点：4最短路径：[0,1,3,4]路径长度（边数）：3=====测试4：起点与终点重合（2→2）=====起点：2，终点：2最短路径：[2]路径长度（边数）：0=====测试5：反向查询路径（4→0）=====起点：4，终点：0最短路径：[4,3,1,0]路径长度（边数）：3=====测试6：6顶点图多分支最短路径（0→5）=====起点：0，终点：5最短路径：[0,1,3,5]路径长度（边数）：37．将迪杰斯特拉算法实现为程序，在连通简单非负赋权图中，求两个顶点之间的最短路。（1）程序代码defdijkstra(adj_matrix,start,end):"""迪杰斯特拉算法求解非负赋权图中两顶点间的最短路径参数:adj_matrix:list[list]，带权邻接矩阵，无边用float('inf')表示，对角线为0start:int，起点顶点编号end:int，终点顶点编号返回:tuple:(最短路径顶点列表,路径总权重)若不可达则返回(None,float('inf'))"""n=len(adj_matrix)#1.顶点编号合法性校验ifstart<0orstart>=norend<0orend>=n:raiseValueError(f"顶点编号非法，有效范围为0~{n-1}")#2.起点与终点重合的特殊情况ifstart==end:return[start],0#3.初始化INF=float('inf')dist=[INF]*n#各顶点到起点的最短距离prev=[-1]*n#最短路径中各顶点的前驱visited=[False]*n#标记顶点是否已确定最短距离dist[start]=0#4.主循环：每次确定一个顶点的最短距离for_inrange(n):#步骤1：找到未访问顶点中距离最小的顶点umin_dist=INFu=-1foriinrange(n):ifnotvisited[i]anddist[i]<min_dist:min_dist=dist[i]u=i#所有剩余顶点都不可达，提前退出ifu==-1:breakvisited[u]=True#步骤2：用顶点u松弛其所有邻接点的距离forvinrange(n):ifnotvisited[v]andadj_matrix[u][v]<INF:ifdist[v]>dist[u]+adj_matrix[u][v]:dist[v]=dist[u]+adj_matrix[u][v]prev[v]=u#5.终点不可达ifdist[end]==INF:returnNone,INF#6.回溯前驱数组，构造最短路径path=[]curr=endwhilecurr!=-1:path.append(curr)curr=prev[curr]path.reverse()returnpath,dist[end]#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(case_name,adj_matrix,start,end):print(f"====={case_name}=====")print(f"起点：{start}，终点：{end}")try:path,total_weight=dijkstra(adj_matrix,start,end)ifpathisnotNone:print(f"最短路径：{path}")print(f"路径总权重：{total_weight}")else:print("两顶点不可达")exceptValueErrorase:print(f"输入错误：{e}")print("-"*50)print()#测试图1：4顶点非负赋权图#边：0-1(2),0-2(5),1-2(1),1-3(3)INF=float('inf')adj_4v=[[0,2,5,INF],[2,0,1,3],[5,1,0,INF],[INF,3,INF,0]]run_test("测试1：0→3（需中转，最短路径0→1→3）",adj_4v,0,3)run_test("测试2：0→2（中转更优，0→1→2）",adj_4v,0,2)run_test("测试3：起点终点重合（2→2）",adj_4v,2,2)run_test("测试4：反向查询（3→0）",adj_4v,3,0)#测试图2：5顶点非负赋权图#边：0-1(4),0-2(2),1-2(1),1-3(5),2-3(8),2-4(10),3-4(2)adj_5v=[[0,4,2,INF,INF],[4,0,1,5,INF],[2,1,0,8,10],[INF,5,8,0,2],[INF,INF,10,2,0]]run_test("测试5：5顶点图0→4（多分支最短路径）",adj_5v,0,4)（2）算例测试=====测试1：0→3（需中转，最短路径0→1→3）=====起点：0，终点：3最短路径：[0,1,3]路径总权重：5=====测试2：0→2（中转更优，0→1→2）=====起点：0，终点：2最短路径：[0,1,2]路径总权重：3=====测试3：起点终点重合（2→2）=====起点：2，终点：2最短路径：[2]路径总权重：0=====测试4：反向查询（3→0）=====起点：3，终点：0最短路径：[3,1,0]路径总权重：5=====测试5：5顶点图0→4（多分支最短路径）=====起点：0，终点：4最短路径：[0,2,1,3,4]路径总权重：108．编程求解旅行商问题。（1）程序代码deftsp_dynamic_programming(dist_matrix,start=0):"""状态压缩动态规划求解旅行商问题（精确最优解）参数:dist_matrix:list[list]，城市间的距离矩阵（对称/非对称均可，非负权）start:int，起点城市编号，默认从0号城市出发返回:tuple:(最短回路顶点序列,回路总长度)"""n=len(dist_matrix)#1.输入合法性校验ifstart<0orstart>=n:raiseValueError(f"起点编号非法，有效城市编号为0~{n-1}")ifn==0:return[],0ifn==1:return[start,start],0INF=float('inf')#状态总数：2^n种访问状态state_count=1<<n#2.初始化DP数组与前驱数组dp=[[INF]*nfor_inrange(state_count)]prev=[[-1]*nfor_inrange(state_count)]#记录路径前驱，用于回溯路径dp[1<<start][start]=0#初始状态：只访问了起点，在起点，距离为0#3.状态转移：遍历所有访问状态formaskinrange(state_count):#遍历当前所在城市i（必须在已访问集合中）foriinrange(n):ifnot(mask&(1<<i))ordp[mask][i]==INF:continue#尝试前往未访问的城市jforjinrange(n):ifmask&(1<<j):#j已访问，跳过continuenew_mask=mask|(1<<j)new_dist=dp[mask][i]+dist_matrix[i][j]ifnew_dist<dp[new_mask][j]:dp[new_mask][j]=new_distprev[new_mask][j]=i#4.计算最终回路：所有城市访问完毕后，返回起点的最短总距离full_mask=(1<<n)-1min_total=INFlast_city=-1foriinrange(n):total=dp[full_mask][i]+dist_matrix[i][start]iftotal<min_total:min_total=totallast_city=i#5.回溯前驱数组，构造完整回路path=[]curr=last_citymask=full_maskwhilecurr!=-1:path.append(curr)pre=prev[mask][curr]mask^=(1<<curr)#移除当前城市的访问标记curr=prepath.reverse()#反转得到从起点出发的顺序path.append(start)#回到起点，形成闭合回路returnpath,min_total#==========测试算例与运行入口==========if__name__=="__main__":defrun_test(case_name,dist_matrix,start=0):print(f"====={case_name}=====")print(f"城市数量：{len(dist_matrix)}，起点城市：{start}")try:path,total=tsp_dynamic_programming(dist_matrix,start)print(f"最短回路：{'→'.join(map(str,path))}")print(f"回路总长度：{total}")exceptValueErrorase:print(f"错误：{e}")print("-"*55)print()#测试1：3城市三角形（简单验证，最短路径为周长）dist_3=[[0,2,3],[2,0,4],[3,4,0]]run_test("测试1：3城市三角形",dist_3)#测试2：4城市经典TSP算例dist_4=[[0,2,9,10],[2,0,6,4],[9,6,0,8],[10,4,8,0]]run_test("测试2：4城市标准算例",dist_4)#测试3：5城市非对称TSP（有向图场景）dist_5=[[0,3,8,2,7],[3,0,4,6,3],[4,4,0,5,8],[2,6,5,0,6],[7,3,8,6,0]]run_test("测试3：5城市赋权完全图",dist_5)#测试4：指定起点为2号城市run_test("测试4：4城市-指定起点2",dist_4,start=2)（2）算例测试=====测试1：3城市三角形=====城市数量：3，起点城市：0最短回路：0→1→2→0回路总长度：9=====测试2：4城市标准算例=====城市数量：4，起点城市：0最短回路：0→1→3→2→0回路总长度：23=====测试3：5城市赋权完全图=====城市数量：5，起点城市：0最短回路：0→3→2→1→4→0回路总长度：21=====测试4：4城市-指定起点2=====城市数量：4，起点城市：2最短回路：2→1→0→3→2回路总长度：239．将深度优先搜索算法实现为程序，求一个连通图的生成树。（1）程序代码defdfs_spanning_tree(adj