数据结构——图结构（Python）

我使用Python中字典dict()方法来存储图结构（这里使用的是邻接表）

举个例子，比如，将一个无向加权图（无向网）进行存储，如下图所示：

该图所对应的邻接表为：

此时，让字典中的键表示各个结点，值则表示各个结点的对应链表（即各个邻接点）。

其中，链表用列表list()来进行存储，而链表中的各个结点用元组tuple()来进行存储：

graph={ 1： [ ( 2 , 2 ), ( 3 , 1) ] ,

             1： [ ( 1 , 2 ), ( 4 , 5) , ( 5 , 4) ] ,

             1： [ ( 1 , 1 ) ] ,

             1： [ ( 2 , 5 ) ] ,

             1： [ ( 2 , 4 ) ] }

具体代码如下：

n=int(input())#输入结点数
a=dict()#用来存储图
vis=dict()#辅助数组，表示图中的各个结点的状态（遍历图时会用到，用来标记是否以读）
for i in range(n-1):#创建图结构
    b=list(map(int,input().split()))
    if not a.get(b[0]):#字典中不存在该点
        a[b[0]]=[(b[1],b[2])]#（b[1]为邻接点，b[2]为权）
    else:#字典中存在该点
        a[b[0]].append((b[1],b[2]))
    if not a.get(b[1]):#字典中不存在该点
        a[b[1]]=[(b[0],b[2])]#（b[1]为邻接点，b[2]为权）
    else:#字典中存在该点
        a[b[1]].append((b[0],b[2]))
    #显示该节点是否以读（0未读，1已读）
    vis[b[0]]=0
    vis[b[1]]=0

注：这里不包括如何对图进行遍历