python 图创建

说明

创建图有3种方式

1，邻接矩阵

2，邻接集合

3，邻接字典

代码实现

# coding=utf8

# 对5个顶点进行排序
a, b, c, d, e = range(5)
# 顶点个数
N = 5

G = [[0] * N for _ in xrange(N)]

# 邻接矩阵
# 存储数据有大量空的数据，全是0的情况，在查找某一个顶点的邻接顶点就会遍历所有的顶点
def add_edge(G, v1, v2):
    G[v1][v2] = G[v2][v1] = 1

add_edge(G, a, b)
add_edge(G, a, e)
add_edge(G, b, e)
add_edge(G, b, d)    
add_edge(G, b, c)
add_edge(G, c, d)
add_edge(G, d, e)

print G


#更多情况，我们是采用邻接集合和邻接字典来存储
# 邻接集合
# 每一个顶点只记录其邻接顶点
G2 = [{b, e},          # a
      {a, e, b, c},    # b
      {b, d},          # c
      {b, c, e},       # d
      {a, b, d}        # e
      ]
print G2

# 带权的边，利用邻接字典存储
G3 = [{b: 4, e: 2},              # a
      {a: 4, e: 3, d: 6, c: 5},  # b
      {b: 5, d: 7},              # c
      {b: 6, c: 7, e: 1},        # d
      {a: 2, b: 3, d: 1}         # e
      ]

print G3