python - [在Python中实现图表] : are lists of connected nodes preferable over dictionaries?

Question

我的任务是创建节点图/ map 。

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。

Q1。我不应该使用连接节点列表而不是内部字典吗？喜欢:

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

第二季度。我是否应该添加所有节点并在连接时将其值设置为 1，否则设置为 0？

Answer 1

Q1:不会。列表字典对于成员资格测试来说速度较慢。您可以通过使用 set 的字典来避免冗余的 1 值。 s。

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

(这对于有向图很有效，其中 LAX->SAE 和 SAE->LAX 价格是独立的。无向图实现起来比较棘手；一个巧妙的技巧是一个键为 2- 的字典元素 frozenset s；但复制数据可能是最简单的。)

问题2:没有理由，浪费(大多数图的边远少于n**2)并且在动态添加/删除节点时很难维护。您可以使用 collections.defaultdict(int)在没有存储 1 的地方模拟 0(注意:访问时它会存储 0)，但我建议只查看 graph[node1 中的 node2 ] 用于连接检查，留下 graph[node1][node2] 用于额外的边缘数据(如果有)。