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

Question

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

Answer 1

如果您不想只使用其中一个可用的图形库

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

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