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]]  

就不写构建方法。

今天的文章python 图论算法（一）分享到此就结束了，感谢您的阅读。