一般python创建有向图与无向图有以下几种方式 一般借助于列表或者字典来创建 有向图每一次建一条边即可 无向图则需要建两次 双向建边 也即a-- b和b-- a 我们可以先考虑有向图的建图方式 首先是分为两大类 第一大类的边没有权重 顶点与顶点之间存在联系 第二大类的边具有权重 处理的方式都是一样的 只是在存储的时候有细微的差别
import collections if __name__ __main__ : print(Solution().process()) # 有向图节点个数为10 n 10 # g中的每一个顶点都是一个列表, 这样就可以往对应顶点添加出边以及对应的权重 g [list() for i in range(n)] # 有向图中存在边: 1- 2 g[1].append(2) # 有向图存在边: 2- 4, 并且权重为5 g[2].append((4, 5)) print(g) n 10 # 列表中的每一个元素为一个字典这种方式比较适合于有向边存在权重的情况 g [dict() for i in range(n)] # 有向图存在边: 3- 4, 并且权重为10 g[3][4] 10 print(g) n 10 g collections.defaultdict(list) # 有向图存在边: 1- 2 g[1].append(2) # 有向图存在边: 1- 2, 并且权重为3 g[1].append((2, 3)) print(g) # 无向图以上面其中一种方式为例, 其余的两种方式也是类似的 n 10 g [list() for i in range(n)] # 1与2之间有一条无向边 g[1].append(2) g[2].append(1) print(g)
