好好聚你狙击贝贝就OK
class Vertex(object):
def __init__(self,data):
self.data = data
self.FirstArc = None
##########################################################
#类名称:Acr
#类说明:定义图中的一条边
#类释义:包含该边的一个顶点adjacent、与该边相关的信息info和
# 与该边依附于相同顶点的另一条边NextArc
##########################################################
class Arc(object):
def __init__(self,adjacent):
self.adjacent = adjacent
self.info = None
self.NextArc = None
##################################################################
#类名称:Graph
#类说明:定义一个图
#类释义:包含该图的类型kind(0无向图,1无向网,2有向图,3有向网)、
# 图中的顶点数VertexNum、边或弧的数目ArcNum和邻接表Vertices
##################################################################
class Graph(object):
def __init__(self,kind):
self.kind = kind
self.VertexNum = 0
self.ArcNum = 0
self.Vertices = []
#############################################
#以邻接表作为存储结构创建有向图或无向图的方法
#############################################
def CreateGraph(self):
#依次输入顶点的值,创建顺序存储结构
print('请依次输入图中各顶点的值,每个顶点值以回车间隔,并以#作为输入结束符:')
data = input('->')
while data != '#':
vertex = Vertex(data)
self.Vertices.append(vertex)
self.VertexNum = self.VertexNum + 1
data = input('->')
#依次输入边或弧的两个顶点,并进行定位
print('请依次输入图中每条边的两个顶点值,两个顶点值以空格作为间隔,每输入一组后进行换行,最终以#结束输入:')
arc = input('->')
while arc != '#':
TailVertex = arc.split()[0] #边或弧的一个顶点
HeadVertex = arc.split()[1] #边或弧的另一个顶点
TailIndex = self.LocateVertex(TailVertex)
HeadIndex = self.LocateVertex(HeadVertex) #定位两个顶点在邻接表中的位置
#将与输入的两个顶点相关联的边插入到顶点的链表当中
self.InsertArc(TailIndex,HeadIndex)
self.ArcNum = self.ArcNum + 1 #边或弧的数目加1
arc = input('->')
#创建成功
print('创建成功!')
##################################
#定位顶点在邻接表中的位置的方法
##################################
def LocateVertex(self,Vertex):
index = 0
while self.Vertices[index].data != Vertex and index < len(self.Vertices):
index = index + 1
return index
##################################
#将图中的边或弧插入邻接表的方法
##################################
def InsertArc(self,TailIndex,HeadIndex):
if self.kind == 0:#无向图
TailArc = Arc(TailIndex)
HeadArc = Arc(HeadIndex)
#对TailVertex,插入HeadVertex
HeadArc.NextArc = self.Vertices[TailIndex].FirstArc #
self.Vertices[TailIndex].FirstArc = HeadArc
#对HeadVertex,插入TailVertex
TailArc.NextArc = self.Vertices[HeadIndex].FirstArc
self.Vertices[HeadIndex].FirstArc = TailArc
elif self.kind == 2:#有向图
#对TailVertex,插入HeadVertex
HeadArc = Arc(HeadIndex)
HeadArc.NextArc = self.Vertices[TailIndex].FirstArc
self.Vertices[TailIndex].FirstArc = HeadArc