时间戳

首页 > 解决方案 > python中映射系统的加权无向图

python - python中映射系统的加权无向图

问题描述

我想知道如何在 python 中为 map 实现加权无向图。地图上有城市和一些道路，它们连接城市并具有各自的权重。

标签： pythonweighted-graph

解决方案

如果您不想只使用其中一个可用的图形库……</p>

表示图的标准方法是邻接表。您可以将其实现为字典，其中键是节点名称（或查找节点的其他 ID），值是边列表。边可以是一些数据结构，为您提供连接节点名称和权重——从元组到 NamedTuple 再到完整的边类。例如，这是一个最小加权图：

places = {
    'A': set([('B', 10), ('C', 5)]),
    'B': set([('D', 3), ('A', 10)]),
    'C': set([('F', 20), ('G', 9), ('A', 5)]),
    'D': set([('B', 3)]),
    'F': set([('C', 20)]),
    'G': set([('C', 9)])
}

您可以判断它是无向的，因为每条边出现两次——在源节点和目标节点的列表中。

这种格式将支持主要的图形算法，如 DFS、BFS、Dijkstra...

这是一个快速而肮脏的深度优先搜索：

places = {
    'A': set([('B', 10), ('C', 5)]),
    'B': set([('D', 3), ('A', 10)]),
    'C': set([('F', 20), ('G', 9), ('A', 5)]),
    'D': set([('B', 3)]),
    'F': set([('C', 20)]),
    'G': set([('C', 9)])
}


def findARoute(start, end, places, visited = None):
    if visited is None:
        visited  = set()

    visited.add(start)

    try:
        edges = places[start]
    except KeyError:
        return # node not in graph

    for edge in edges:
        node, wieght = edge

        if node not in visited:
            print(f'Trying {start} -> {node}')
            if node == end:
                print(f'Found: {end}')
                return
            findARoute(node, end, places, visited)

findARoute('A', 'G', places)

印刷：

Trying A -> B
Trying B -> D
Trying A -> C
Trying C -> F
Trying C -> G
Found: G

推荐阅读