在 Python 中实现没有库的图形

Question

我是 Python 的新手，正在尝试在不使用库的情况下构建有向图。有人可以确认我是否正确理解了这个例子吗？

from collections import defaultdict 
class Graph:
    def __init__(graph):
        graph.dict = defaultdict(list)
    def add(graph,node,adjacent_node): 
        graph.dict[node].append(adjacent_node)    #line 6
        graph.dict[adjacent_node].append(node)    #line 7

graph = Graph()
graph.add('1','2') 
graph.add('2','5') 
graph.add('2','3') 
graph.add('4','5') 
graph.add('4','3') 
graph.add('6','4') 
graph.add('6','5')
print('Dictionary:',graph.dict)

_____
Output:
Dictionary: defaultdict(<class 'list'>, {'1': ['2'], '2': ['1', '5', '3'], '5': ['2', '4', '6'], '3': ['2', '4'], '4': ['5', '3', '6'], '6': ['4', '5']})

根据我的理解，这个例子正在构建一个无向图

在第 6 行，他们添加了从原始节点到相邻节点的路径
在第 7 行，他们添加了从相邻节点 BACK 到原始节点的路径

这是正确的吗？

如果这些是节点，我也有点困惑，为什么它们需要到下一个节点的路径？一旦我创建了一个 addEdges 函数，边会不会处理这个问题，或者这个函数是否足以同时添加节点和边？

example source

Answer 1

您在这里使用的是 adjacency list 图形表示法。

在您当前的实现中，add 创建了一条从 node 到 adjacent_node 的无向边。 “无向边”意味着如果你在node，你可以过渡到adjacent_node，如果你在adjacent_node，你可以过渡到node。这是双向关系。

add 也会创建这些节点（如果由于 defaultdict 而这些节点尚不存在）。将节点视为字典中的键，将边视为与节点关联的列表中的元素。

如果你想要一个有向图，这意味着 add 应该只创建一条从源到目的地的边：

def add(graph,node,adjacent_node): 
    graph.dict[node].append(adjacent_node)
    # graph.dict[adjacent_node].append(node)  # <- skip if you want a directed graph

无需在此处添加更多函数来表示图形。

在 Python 中实现没有库的图形

Implementing a graph without a library in Python

python

graph

directed-graph

undirected-graph