Python：从带括号的边创建图节点

Question

我正在尝试从一个输入创建一个图，输入的格式如下：

(1 2) (2 3) (3 4) (4 1) 

上面的表示方式是用空格分开的，每个括号里的参数代表两个节点之间的连接。我不太确定哪种矩阵表示法更好用……是 邻接矩阵 还是 邻接链表？

有没有什么想法可以帮助我解析这样的输入？比如，怎么把它直接存储到矩阵里？

提前谢谢大家！

Answer 1

你可以这样解析它

points = re.findall("\((\d+) (\d+)\)","(1 2) (2 3) (3 4) (4 1) ")

Answer 2

我建议你建立一个字典，这个字典可以把每个节点和它连接的节点集合起来。这里假设你的连接是单向的，也就是说信息只能从一个节点流向另一个节点。

info = '(1 2) (2 3) (3 4) (4 1)'
info = info.replace('(','').replace(')','')
info = info.split(' ')
edges={};
for i in range(1,len(info)):
    if i%2 == 1:
        startnode = info[i-1]
        endnode = info[i]
        if startnode not in edges:
            edges[startnode] = set()
        edges[startnode].add(endnode)

Answer 3

从使用的方便性来看，矩阵邻接法更好，因为在两个节点之间检测边的时间是O(1)，也就是非常快。如果你的网络很大而且稀疏，使用矩阵邻接法会浪费很多空间，因为里面会有很多零，这时候你就应该选择链表邻接法。对于你来说，因为图比较小，所以这两种方法差别不大。