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

Question

我想知道如何在 python 中为地图实现加权无向图。地图有城市和一些道路，城市之间 link 并且具有各自的权重。

Answer 1

如果您不想只使用可用的图形库之一……

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

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

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

Weighted undirected graph for mapping system in python

python

weighted-graph