博客

本文使用的是列表存储的图结点，列表中的每一个元素是图的一个结点对象，其中有两部分：一个数据域、一个指针域；数据域存储当前结点的值，指针域存储的是和当前结点邻接的结点的位置（边学习边写，不足之处多多留言指点）

'''图的邻接表方法表示'''

#图的结点类
class GraphNode(object):

    #初始化图的结点（图的结点有两部分：数据域、指针域）
    def __init__(self,_elem = None):
        self._elem = _elem
        self._next = None

#图
class Graph(object):

    #初始化一个队列
    def __init__(self):
        self._graph = []

    #创建一个图的顶点
    def createPeak(self,new_code):
        self._graph.append(new_code)
        return self._graph

    #创建一个图的边(参数为两个顶点)
    def createSide(self):
        # 找到图中的每一个结点
        for node in self._graph:
            graph_node = node
            print("请输入%s的邻接点（以-1结束）" % graph_node._elem)
            while True:
                # 初始化每个结点的邻接点
                _graph_node = GraphNode()
                end = input("请输入：")
                if end == "-1":
                    break
                else:
                    #临时列表图中结点的值，以方便后序判断
                    temp = []
                    for i in self._graph:
                        temp.append(i._elem)
                    #如果输入当前结点的邻接点不存在，报错
                    if end not in temp:
                        print('输入有误...')
                        continue
                    #如果输入的值和当前的值相同，重新输入
                    elif end == graph_node._elem:
                        print('与当前结点相同....')
                        continue
                    else:
                        # 新建邻接点
                        _graph_node._elem = end
                        # 指针指向后移
                        _graph_node._next = graph_node._next
                        graph_node._next = _graph_node
                        graph_node = graph_node._next

    # 打印出邻接表
    def print_graph(self):
        #遍历当前结点列表
        for node in self._graph:
            print('顶点%s的邻接链表：' % node._elem,node._elem, end='')
            #每一个结点后边都有一个邻接链表，使用while循环遍历打印，当指针域为None时，当前结点的链表遍历完成
            while node._next != None:
                print('-->',node._next._elem, end='')
                node = node._next
            print('\n')


if __name__ == '__main__':
    count = int(input('输入顶点个数:'))
    s = Graph()
    #创建结点
    for i in range(0,count):
        peak_node = input('输入顶点:')
        #将输入的结点实例化之后添加到图的链表中
        peak = GraphNode(peak_node)
        s.createPeak(peak)
    print('图中的顶点:',end=' ')
    for i in s._graph:
        print(i._elem,end=' ')
    print()

    s.createSide()
    s.print_graph()