即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

图的实现(python)

编程语言 kan2281123066 106℃ 0评论

比如有这么一张图:

这里写图片描述

(1)可以用字典和列表来表示

graph = {'V0':['V1','V5'],
         'V1':['V2'],
         'V2':['V3'],
         'V3':['V4','V5'],
         'V4':['V0'],
         'V5':['V2','V4']}

找到一条路径:

def find_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        for node in graph[start]:
            if node not in path:
                newpath = find_path(graph, node, end, path)
                if newpath: return newpath
        return None

找到所有路径:

def find_all_paths(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return [path]
        if not graph.has_key(start):
            return []
        paths = []
        for node in graph[start]:
            if node not in path:
                newpaths = find_all_paths(graph, node, end, path)
                for newpath in newpaths:
                    paths.append(newpath)
        return paths

找到最短路径:

def find_shortest_path(graph, start, end, path=[]):
        path = path + [start]
        if start == end:
            return path
        if not graph.has_key(start):
            return None
        shortest = None
        for node in graph[start]:
            if node not in path:
                newpath = find_shortest_path(graph, node, end, path)
                if newpath:
                    if not shortest or len(newpath) < len(shortest):
                        shortest = newpath
        return shortest

(2) 邻接矩阵

会将每个结点可能的邻居位置排成一行(也就是一个数组,用于对应图中每一个结点),然后用某种值(如True或False)来表示相关结点是否为当前结点的邻居。为了让矩阵具有更好的可读性,我们将会用1和0来充当所谓的真值(也可用True和False)。

v0,v1,v2,v3,v4,v5=range(6)
N=[[0,1,0,0,0,1],#v0
   [0,0,1,0,0,0],#v1
   [0,0,0,1,0,0],#v2
   [0,0,0,0,1,1],#v3
   [1,0,0,0,0,0],#v4 
   [0,0,1,0,1,0]]#v5 

   >>> N[v0][v1]
1
>>> sum(N[v0])
2

将邻接矩阵扩展成允许对边进行加权处理:在原来存储真值的地方直接存储相关的权值即可。例如,对于边(u,v)来说,我们只需要将N[u][v]处的True替换成w(u,v)即可,我们通常会将一些不存在的边的权值设置为无穷大。


对角线上的值依旧应该全为0,任何节点到自身的距离都应该始终为0。

把上面的代码改为:

v0,v1,v2,v3,v4,v5=range(6)  
inf=float('inf')  
w=N=[[inf,5,inf,inf,inf,2],#v0  
   [inf,inf,4,inf,inf,inf],#v1
   [inf,inf,inf,9,inf,inf],#v2
   [inf,inf,inf,inf,7,3],#v3
   [1,inf,inf,inf,inf,inf],#v4
   [inf,inf,1,inf,8,inf]]#v5 
>>>w[v0][v1]
Out[6]: 
5
>>>w[v2][v1]
Out[7]: 
inf

转载请注明:CodingBlog » 图的实现(python)

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情