数据结构与算法实验—— 图的基本操作_图的基本算法实验总结

1. 实验目的

理解图的十字链表这一存储结构，并掌握有向图的基本操作。

2. 实验介绍

 掌握图的基本概念及相关术语和性质，掌握图的邻接矩阵和邻接表表示法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。熟练掌握图的两种搜索路径的遍历：深度优先搜索和广度优先搜索的算法。掌握构造最小生成树的两种算法及拓扑排序算法的思想，掌握迪杰斯特拉算法。了解关键路径的概念和求解方法，了解弗洛伊德算法。

3.实验内容

 创建名为 ex060901_01.py 的文件，在文件中定义 3 个类，第一个是顶点的结点类，

第二个是弧的结点类，第三个是图类，该类包含存储有向图的十字链表及有向图的基本

操作。请按以下步骤设计实现代码并验证之。

（1） 创建一个图 6-1（主教材 P317 图 6-45）所示的有向图，并使用十字链表存

储。

（2）计算图中顶点的总数和弧的总数。

（3）计算每一个顶点的入度、出度和度。

（4）添加一条弧<D,C>。

（5）获取顶点 D 邻接到的第一个顶点，并将其值输出

4. 实验步骤与代码

    class CircularSequenceQueue:
        def __init__(self):
            self.MaxQueueSize=4
            self.s=[None for x in range(0,self.MaxQueueSize)]
            self.front=0
            self.rear=0
     
        def InitQueue(self,Max):
            self.MaxQueueSize=Max
            self.s=[None for x in range(0,self.MaxQueueSize)]
            self.front=0
            self.rear=0
           
        def QueueVisit(self,element):
            print(element,end=' ')
     
        def IsEmptyQueue(self):
            if self.front==self.rear:
                 iQueue=True
            else:
                 iQueue=False
            return iQueue
     
        def EnQueue(self,x):
              if (self.rear+1)%self.MaxQueueSize!=self.front:
                  self.rear=(self.rear+1)%self.MaxQueueSize
                  self.s[self.rear]=x
              else:
                print("队列已满，无法入队")
                return  
      
        def DeQueue(self):
            if self.IsEmptyQueue():
               print("队列为空，无法出队")
               return
            else:
                self.front=(self.front+1)%self.MaxQueueSize
                return self.s[self.front]
          
        def QueueTraverse(self):
            if self.IsEmptyQueue():
                print("队列为空，队列无元素可以访问")
                return
            else:
                if  self.front<self.rear:
                    i=self.front+1
                    while i<self.rear:
                        self.QueueVisit(self.s[i])
                        i=i+1
                    self.QueueVisit(self.s[self.rear])
                else:
                    i=self.front+1
                    while i<self.MaxQueueSize:
                        self.QueueVisit(self.s[i])
                        i=i+1
                    i=0
                    while i<=self.rear:
                        self.QueueVisit(self.s[i])
                        i=i+1
               
        def GetHead(self):
            if self.IsEmptyQueue():
                print("队列为空，无法输出队首元素")
                return
            else:
                return self.s[(self.front+1)%self.MaxQueueSize]
     
        def GetQueueLength(self):
            if self.IsEmptyQueue():
                print("队列为空，队列长度为零")
                return
            else:
                return (self.rear-self.front+self.MaxQueueSize)%self.MaxQueueSize
     
    class Vertex(object):
        def __init__(self,data):
            self.data = data
            self.FirstArc = None
     
    class Arc(object):
        def __init__(self,adjacent):
            self.adjacent = adjacent
            self.info = None
            self.NextArc = None
     
    class Graph(object):
        def __init__(self,kind):
            self.kind = kind
            self.VertexNum = 0
            self.ArcNum = 0
            self.Vertices = []
            self.indegree = {}
            self.outdegree = {}
     
        def CreateGraph(self):
            print('请依次输入图中各顶点的值，每个顶点值以回车间隔，并以#作为输入结束符：')
            data = input('->')
            while data is not '#':
                vertex = Vertex(data)
                self.Vertices.append(vertex)
                self.indegree[data] = 0
                self.outdegree[data] = 0
                self.VertexNum = self.VertexNum + 1
                data = input('->')
            print('请依次输入图中每条边的两个顶点值，两个顶点值以空格作为间隔，每输入一组后进行换行，最终以#结束输入：')
            arc = input('->')
            while arc is not '#':
                TailVertex = arc.split()[0]
                HeadVertex = arc.split()[1]
                self.indegree[TailVertex] = self.indegree[TailVertex] + 1
                self.outdegree[HeadVertex] = self.outdegree[HeadVertex] + 1
                TailIndex = self.LocateVertex(TailVertex)
                HeadIndex = self.LocateVertex(HeadVertex)
                self.InsertArc(TailIndex,HeadIndex)
                self.ArcNum = self.ArcNum + 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 is 0:
                TailArc = Arc(TailIndex)
                HeadArc = Arc(HeadIndex)
                HeadArc.NextArc = self.Vertices[TailIndex].FirstArc
                self.Vertices[TailIndex].FirstArc = HeadArc
                TailArc.NextArc = self.Vertices[HeadIndex].FirstArc
                self.Vertices[HeadIndex].FirstArc = TailArc
            elif self.kind is 2:
                HeadArc = Arc(HeadIndex)
                HeadArc.NextArc = self.Vertices[TailIndex].FirstArc
                self.Vertices[TailIndex].FirstArc = HeadArc
     
        def GetFirstAdjacentVertex(self,Vertex):
            FirstArc = self.Vertices[Vertex].FirstArc
            if FirstArc is not None:
                return FirstArc.adjacent
     
        def GetNextAdjacentVertex(self,Vertex,Adjacent):
            ArcLink = self.Vertices[Vertex].FirstArc
            while ArcLink is not None:
                if ArcLink.adjacent is Adjacent:
                    if ArcLink.NextArc is not None:
                        return ArcLink.NextArc.adjacent
                    else:
                        return None
                else:
                    ArcLink = ArcLink.NextArc
     
        def VisitVertex(self,Vertex):
            print(self.Vertices[Vertex].data,end='')
            
        def BFSTraverse(self):
            visited=[]
            index = 0
            Queue=CircularSequenceQueue()
            Queue.InitQueue(10)
            while index < self.VertexNum:
                visited.append('False')
                index = index + 1
            index = 0
            while index < self.VertexNum:
                if visited[index] is 'False':
                    visited[index] = 'True'
                    self.VisitVertex(index)
                    Queue.EnQueue(index)
                    while Queue.IsEmptyQueue() is False:
                        tVertex = Queue.DeQueue()
                        NextAdjacent = self.GetFirstAdjacentVertex(tVertex)
                        while NextAdjacent is not None:
                            if visited[NextAdjacent] is 'False':
                                visited[NextAdjacent] = 'True'
                                self.VisitVertex(NextAdjacent)
                                Queue.EnQueue(NextAdjacent)
                            NextAdjacent = self.GetNextAdjacentVertex(tVertex,NextAdjacent)
                index = index + 1
     
     
    if __name__ =='__main__':
        graph = Graph(2)
        print('要构建如下图所示的图：')
        print('A  →  B')
        print('↓↘  ↗ ↓')
        print('↓  E  ↓')
        print('↓↙  ↘ ↓')
        print('C     D')
        graph.CreateGraph()
        print('该图顶点数为',graph.VertexNum,'个','弧数为',graph.ArcNum,'个')
        print('      ',end='')
        for i in range(len(graph.indegree)):
            print(list(graph.indegree.keys())[i],end=' ')
        print()
        print('入度',end=' ')
        for i in range(len(graph.indegree)):
            print(graph.indegree[list(graph.indegree.keys())[i]],end=' ')
        print()
        print('出度',end=' ')
        for i in range(len(graph.indegree)):
            print(graph.outdegree[list(graph.indegree.keys())[i]],end=' ')
        print()
        print('  度',end=' ')
        for i in range(len(graph.indegree)):
            print(graph.indegree[list(graph.indegree.keys())[i]] + graph.outdegree[list(graph.indegree.keys())[i]],end=' ')
        print()
        print('插入弧<D,C>')
        graph.InsertArc(3,2)
        print('将D邻接的第一个顶点为：',end=' ')
        print(chr(graph.GetFirstAdjacentVertex(3)+64))
        print('广度优先遍历图的结果如下:',end=' ')
        graph.BFSTraverse()

5.实验结果