一、实验目的
1．掌握生成树和最小生成树方法，包括普里姆算法设计和克鲁斯卡尔算法设计；
2．掌握求解图的最短路径方法，包括单源最短路径的狄克斯特拉算法设计和多源最短路径的弗洛伊德算法设计；
3．灵活运用图数据结构解决一些综合的应用问题。
二、实验环境
1．Windows操作系统的计算机
2．Python3.7环境平台和PyCharm编辑器
三、实验说明
1．实现最小生成树和图的最短路径算法程序设计方法。
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。
3．自主编写程序，必要时参考相关资料。
4．实验学时：2学时
四、实验内容和步骤
1．实验内容
（1） 编写一个实验程序，利用课本P261图7.31(a)的边数组，采用Prim算法求出以顶点0为起始顶点的一棵最小生成树。
参考思路：
from MatGraph import MatGraph,INF,MAXV
def Prim(g,v): #求最小生成树
……
#主程序
g=MatGraph()
n,e=6,10
a=__________ #图7.31(a)的边数组
g.CreateMatGraph(a,n,e)
print("图G1")
g.DispMatGraph()
print("求解结果");
Prim(g,0)
（2）编写一个图的实验程序，给定一个连通图，采用邻接表G存储，输出根结点为0的一棵深度优先生成树和一棵广度优先生成树，用相关数据进行测试。
参考思路：
from AdjGraph import AdjGraph,MAXV,INF #引用邻接表存储结构
from collections import deque #引用双端队列deque
def DFSTree(G,v): #邻接表G中从顶点v出发的深度优先遍历
global visited
global T1
visited[v]=1
for j in range(len(G.adjlist[v])):
w=G.adjlist[v][j].adjvex
if visited[w]==0:
T1.append([v,w])
DFSTree(G,w)
def BFSTree(G,v): #邻接表G中从顶点v出发的广度优先遍历
global T2
qu=deque()
visited[v]=1
qu.append(v)
while len(qu)>0:
v=qu.popleft()
for j in range(len(G.adjlist[v])):
w=G.adjlist[v][j].adjvex
if visited[w]==0:
T2.append([v,w])
visited[w]=1
qu.append(w)
if __name__ == '__main__':
G=AdjGraph()
n,e=10,12
a=[ [0,1,1,1,0,0,0,0,0,0],
[1,0,0,0,1,1,0,0,0,0],
[1,0,0,1,0,1,1,0,0,0],
[1,0,1,0,0,0,0,1,0,0],
[0,1,0,0,0,0,0,0,0,0],
[0,1,1,0,0,0,0,0,0,0],
[0,0,1,0,0,0,0,1,1,1],
[0,0,0,1,0,0,1,0,0,0],
[0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,1,0,0,0] ]
print()
print(" (1)由a创建邻接表G")
G.CreateAdjGraph(a,n,e)
print(" G:")
G.DispAdjGraph()
print(" (2)DFSTree构造深度优先生成树T1")
T1=[]
visited=[0]*MAXV
DFSTree(G,0)
print(" T1:",T1)
print(" (3)BFSTree构造广度优先生成树T2")
T2=[]
visited=[0]*MAXV
BFSTree(G,0)
print(" T2:",T2)
2．实验步骤
（1）分析实验内容，写出程序大致框架或完整的程序代码。
（2）进入Python集成环境。
（3）编辑程序并进行保存。
（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。
（5）检查程序输出结果。
五、实验代码与结果（程序运行代码及其结果）
1． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
from MatGraph import MatGraph, INF, MAXV
def Prim(g,v): #求最小生成树
lowcost=[0]*MAXV #建立数组lowcost
closest=[0]*MAXV #建立数组closest
for i in range(g.n): #给lowcost[]和closest[]置初值
lowcost[i]=g.edges[v][i]
closest[i]=v
for i in range(1,g.n): #找出最小生成树的n-1条边
min=INF
k=-1
for j in range(g.n): #在(V-U)中找出离U最近的顶点k
if lowcost[j]!=0 and lowcost[j]<min:
min=lowcost[j]
k=j #k记录最小顶点的编号
print("(%d,%d):%d" %(closest[k],k,+min),end=' ') #输出最小生成树的边
lowcost[k]=0 #将顶点k加入U中
for j in range(g.n): #修改数组lowcost和closest
if lowcost[j]!=0 and g.edges[k][j]<lowcost[j]:
lowcost[j]=g.edges[k][j]
closest[j]=k
#主程序
#主程序
g=MatGraph()
n,e=6,10
a=[
[0, 3, 1, 4, INF, INF],
[3, 0, 5, INF, 3, INF],
[1, 5, 0, 5, 2, 1],
[4, INF, 5, 0, 7, 6],
[INF, 3, 2, 7, 0, 6],
[INF, INF, 3, 6, 6, 0]
] #图7.31(a)的边数组
g.CreateMatGraph(a,n,e)
print("图G1")
g.DispMatGraph()
print("求解结果");
Prim(g,0)
2． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
from AdjGraph import AdjGraph,MAXV,INF #引用邻接表存储结构
from collections import deque #引用双端队列deque
def DFSTree(G,v): #邻接表G中从顶点v出发的深度优先遍历
global visited
global T1
visited[v]=1
for j in range(len(G.adjlist[v])):
w=G.adjlist[v][j].adjvex
if visited[w]==0:
T1.append([v,w])
DFSTree(G,w)
def BFSTree(G,v): #邻接表G中从顶点v出发的广度优先遍历
global T2
qu=deque()
visited[v]=1
qu.append(v)
while len(qu)>0:
v=qu.popleft()
for j in range(len(G.adjlist[v])):
w=G.adjlist[v][j].adjvex
if visited[w]==0:
T2.append([v,w])
visited[w]=1
qu.append(w)
if __name__ == '__main__':
G=AdjGraph()
n,e=10,12
a=[ [0,1,1,1,0,0,0,0,0,0],
[1,0,0,0,1,1,0,0,0,0],
[1,0,0,1,0,1,1,0,0,0],
[1,0,1,0,0,0,0,1,0,0],
[0,1,0,0,0,0,0,0,0,0],
[0,1,1,0,0,0,0,0,0,0],
[0,0,1,0,0,0,0,1,1,1],
[0,0,0,1,0,0,1,0,0,0],
[0,0,0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,1,0,0,0] ]
print()
print(" (1)由a创建邻接表G")
G.CreateAdjGraph(a,n,e)
print(" G:")
G.DispAdjGraph()
print(" (2)DFSTree构造深度优先生成树T1")
T1=[]
visited=[0]*MAXV
DFSTree(G,0)
print(" T1:",T1)
print(" (3)BFSTree构造广度优先生成树T2")
T2=[]
visited=[0]*MAXV
BFSTree(G,0)
print(" T2:",T2)
