首页 > 编程语言 > 详细

python 图论算法(一)

时间:2015-03-27 17:25:55      阅读:440      评论:0      收藏:0      [点我收藏+]


       学习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 图论算法(一)

原文:http://blog.csdn.net/u010352695/article/details/44678519

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!