一、实验目的
1．熟悉图的相关概念，包括有向图、无向图、完全图、子图、路径、简单路径、路径长度、回路等定义；
2．掌握图的各种存储结构，主要包括邻接矩阵和邻接表的相关算法设计；
3．掌握图的基本运算算法设计；
4．了解图的遍历过程，包括深度优先遍历和广度优先遍历。
二、实验环境
1．Windows操作系统的计算机
2．Python3.7环境平台和PyCharm编辑器
三、实验说明
1．实现图的两种存储结构相关的算法程序设计方法。
2．实验中如无特别说明，均要求使用脚本（.py）方式编写代码。
3．自主编写程序，必要时参考相关资料。
4．实验学时：2学时
四、实验内容和步骤
1．实验内容
编写一个图的实验程序，设计邻接表类AdjGraph和邻接矩阵类MatGraph，由带权有向图的边数组a创建邻接表G，由G转换为邻接矩阵g，再由g转换为邻接表G1，输出G、g和G1，用相关数据进行测试。
参考思路：
import copy
MAXV=100 #表示最多顶点个数
INF=0x3f3f3f3f #表示∞
class ArcNode: #边结点
def __init__(self,adjv,w): #构造方法
……
class AdjGraph: #图邻接表类
def __init__(self,n=0,e=0): #构造方法
……
def CreateAdjGraph(self,a,n,e): #通过数组a、n和e建立图的邻接表
……
def DispAdjGraph(self): #输出图的邻接表
……
class MatGraph: #图邻接矩阵类
def __init__(self,n=0,e=0): #构造方法
……
def CreateMatGraph(self,a,n,e): #通过数组a、n和e建立图的邻接矩阵
……
def DispMatGraph(self): #输出图
……
def MatToAdj(g): #由图的邻接矩阵转换为邻接表
G=AdjGraph(g.n,g.e)
for i in range(g.n):
adi=[]
for j in range(g.n):
if g.edges[i][j]!=0 and g.edges[i][j]!=INF:
p=ArcNode(j,g.edges[i][j])
adi.append(p)
G.adjlist.append(adi)
return G
def AdjToMat(G): #由图的邻接表转换为邻接矩阵
g=MatGraph(G.n,G.e)
g.edges=[[INF]*g.n for i in range(g.n)]
for i in range(g.n):
g.edges[i][i]=0
for i in range(g.n):
for p in G.adjlist[i]:
g.edges[i][p.adjvex]=p.weight
return g
if __name__ == '__main__':
G=AdjGraph()
n,e=__,___
a=[____________]
print()
print(" (1)由a创建邻接表G")
__________________
print(" G:")
__________________
print(" (2)G->g")
__________________
print(" g:")
__________________
print(" (3)g->G1")
__________________
print(" G1:")
__________________
2．实验步骤
（1）分析实验内容，写出程序大致框架或完整的程序代码。
（2）进入Python集成环境。
（3）编辑程序并进行保存。
（4）运行程序，若有错误，修改错误后再次运行，如此反复进行到不显示出错为止。
（5）检查程序输出结果。
五、实验代码与结果（程序运行代码及其结果）
1． （1）给出算法的基本设计思想。
（2）根据设计思想，采用Python语言描述算法，关键之处给出注释。
import copy
MAXV=100 #表示最多顶点个数
INF=0x3f3f3f3f #表示∞
class ArcNode: #边结点
def __init__(self, adjv, w): #构造方法
self.adjvex = adjv #邻接点编号
self.weight = w #边的权值
class AdjGraph: #图邻接表类
def __init__(self,n=0,e=0): #构造方法
self.n = n #顶点数
self.e = e #边数
self.adjlist = [] #邻接表数组
def CreateAdjGraph(self,a,n,e): #通过数组a、n和e建立图的邻接表
self.n = n
self.e = e
for i in range(n):
adi = []
for j in range(n):
if a[i][j] != 0 and a[i][j] != INF:
p = ArcNode(j,a[i][j])
adi.append(p)
self.adjlist.append(adi)
def DispAdjGraph(self): #输出图的邻接表
for i in range(self.n):
print(" 顶点 %d：" %(i), end='')
for p in self.adjlist[i]:
print(" -> %d(%d)" %(p.adjvex, p.weight), end='')
print("->^")
class MatGraph: #图邻接矩阵类
def __init__(self,n=0,e=0): #构造方法
self.edges=[] #邻接矩阵数组
self.vexs=[] #vexs[i]存放顶点i的信息，暂时未用
self.n=n #顶点数
self.e=e #边数
def CreateMatGraph(self,a,n,e): #通过数组a、n和e建立图的邻接矩阵
self.n=n #置顶点数和边数
self.e=e
self.edges=copy.deepcopy(a) #深拷贝
def DispMatGraph(self): #输出图的邻接矩阵
for i in range(self.n):
for j in range(self.n):
if self.edges[i][j]==INF:
print("%4s"%("∞"),end=' ')
else:
print("%5d" %(self.edges[i][j]),end=' ')
print()
def MatToAdj(g): #由图的邻接矩阵转换为邻接表
G=AdjGraph(g.n,g.e)
for i in range(g.n):
adi=[]
for j in range(g.n):
if g.edges[i][j]!=0 and g.edges[i][j]!=INF:
p=ArcNode(j,g.edges[i][j])
adi.append(p)
G.adjlist.append(adi)
return G
def AdjToMat(G): #由图的邻接表转换为邻接矩阵
g=MatGraph(G.n,G.e)
g.edges=[[INF]*g.n for i in range(g.n)]
for i in range(g.n):
g.edges[i][i]=0
for i in range(g.n):
for p in G.adjlist[i]:
g.edges[i][p.adjvex]=p.weight
return g
if __name__ == '__main__':
G=AdjGraph()
n,e=6,6
a=[[1,3,1,4,INF,INF],
[1,3,1,INF,4,INF],
[5,2,0,5,2,1],
[8,INF,8,8,INF,8],
[INF,6,6,INF,6,6],
[INF,INF,9,9,9,9]]
print()
print(" (1)由a创建邻接表G")
G.CreateAdjGraph(a,n,e)
print(" G:")
G.DispAdjGraph()
print(" (2)G->g")
g=AdjToMat(G)
print(" g:")
g.DispMatGraph()
print(" (3)g->G1")
G1=MatToAdj(g)
print(" G1:")
G1.DispAdjGraph()
