python 图论算法(一)

学习Python有一段时间了，看了几本书，大部分时间都是拿它写一些小的脚本，处理数据，最近用Python实现了几个常见的图论算法。第一部分就是图的存储和建立。

方法一，用矩阵存储。所谓矩阵就是二维数组。Python的二维数组用起来更加随意和简单。写了一个很low的控制台输入建立图的方法。一时间也没想起其他好的方法。

用二维数组存储，对算法的实现很有帮助。

def buildgraph():

n = input()

m = input()

inf = 100000

graph = []

for i in range(n):

graph.append([])

for j in range(n):

if(i = j):

graph[i].append(0)

else:

graph[i].append(inf)

for k in range(m):

a = input()

b = input()

w = input()

graph[a][b] = graph[b][a] = w

return graph

先输入节点数n，再输入边的数量m。注意我们建立的是无向图。然后先构建一个N x N的二维数组并且全部赋值为inf。意为边的大小都是无限大。接下来输入m条边，边的表示用a b w 表示(a,b)为起点，w为权重。

第二种方法，用边级的形式。

edge = [[1,2,1],[1,2,3],[1,3,2],[2,3,1],[2,4,4],[3,4,2]]

就不写构建方法。