[在python中实现图形]：连接节点的列表比字典更可取吗？

Question

我的任务是创建节点的图形/地图。你知道吗

GRAPH = {}

""" ===================================================================
    This function makes a network out of the two nodes
    node1, node2 and puts them in a dictionary: graph
    ---------------------
    node1 : Dictionary
        key: node2 [neighbouring node]
        value: 1
    ---------------------
    node2 : Dictionary
        key: node1 [neighbouring node] 
        value: 1
===================================================================== """
def make_link(graph, node1, node2):
    if node1 not in graph:
        graph[node1] = {}
    (graph[node1])[node2] = 1
    if node2 not in graph:
        graph[node2] = {}
    (graph[node2])[node1] = 1
    return graph

flights = []
flights.append(("LAX","DFW"))
flights.append(("SAE","LAX"))
flights.append(("ORD","LAX"))
flights.append(("ORD","SAE"))

for (x,y) in flights:
    make_link(GRAPH, x, y)

print GRAPH

输出：

codewingx@CodeLair:~/repo/python/Graphs$ python map.py
{'DFW': {'LAX': 1}, 'LAX': {'DFW': 1, 'ORD': 1, 'SAE': 1}, 'ORD': {'LAX': 1, 'SAE': 1}, 'SAE': {'ORD': 1, 'LAX': 1}}

我发现它是多余的，因为只有连接的节点的值是1。你知道吗

问题1。我不应该使用连接节点的列表而不是内部字典吗？ 比如：

{'DFW': ['LAX'], 'LAX': ['DFW', 'ORD', 'SAE'], 'ORD':['LAX','SAE'],'SAE':['ORD','LAX']}

问题2。我是否应该添加所有节点，并在连接到其他节点0时将它们的值设为1？你知道吗

Answer 1

问题1：没有。成员资格测试的列表记录速度较慢。您可以使用sets的dict来避免多余的1值

然而，在处理图形时，我们经常需要与节点和边关联的额外信息（“标签”、“着色”）。例如，在您的示例中，您可以存储每个边的航班价格或持续时间—它自然会取代1

（这适用于有向图，其中LAX->；SAE和SAE->；LAX价格是独立的。无向图更难实现；一个简洁的技巧是dict，它的键是2元素frozenset；但复制数据可能最简单。）

问题2：没有理由这样做，浪费（大多数图的边数远远少于n**2）并且在动态添加/删除节点时很难维护。您可以使用^{}来模拟0，只要您没有存储1（注意：访问时它将存储0），但我建议只查看node2 in graph[node1]进行连接检查，而留下graph[node1][node2]进行额外的边缘数据（如果有的话）。你知道吗