创建一个无向图，给定一个列表。

Question

我有一个列表：

entry=['A','B','C','null','B','A','D','null','E','F']

相邻的字母（顶点）形成一条边。'null'是分隔符。

每条边的权重为1。边(A,B)的权重为2，因为它出现了两次。

为了可视化，上面的列表将变成这个图：

我想创建一个类似于邻接表的字典。

dict= {
'A':{'B':2,'D',1},
'B':{'A':2,'C':1},
'C':{'B':1},
'D':{'A':1},
'E':{'F':1},
'F':{'E':1}
}

第一个键是一个顶点，第二个键是与其相邻的顶点及其权重值。

如何得到上述图形。如果有任何其他更好的表示方式，请提供帮助。

- Eric Klaus

---

你能先展示一下你尝试的代码吗？只需要简单地遍历每个组并将一个数字添加到字典中的每个计数器上似乎很容易做到。 - JBernardo

@JBernardo，我只是想像上面那样得到邻接表，并将其用于进一步的计算。代码很复杂，我将其简化为上述问题，以便更容易理解。这可能很琐碎，但我总是无法理解。 - Eric Klaus

Answer 1

一种解决方案是将您的entry列表缩减为图形字典，因为reduce（无累加器）每次查看2个相邻元素：

可以reduce函数来实现这个功能。

from functools import reduce

graph = {}

def add_edge(u, v):
    if u != 'null' and v != 'null':
        if u in graph:
            graph[u][v] = graph[u].get(v, 0) + 1
        else:
            graph[u] = {v: 1}
        if v in graph:
            graph[v][u] = graph[v].get(u, 0) + 1
        else:
            graph[v] = {u: 1}
    return v

entry = ['A','B','C','null','B','A','D','null','E','F']
reduce(add_edge, entry)

print(graph)
# {'B': {'A': 2, 'C': 1}, 'E': {'F': 1}, 'F': {'E': 1}, 'C': {'B': 1}, 'A': {'B': 2, 'D': 1}, 'D': {'A': 1}}

编辑:

一种更为"纯粹"的降低方式是将相邻的元素压缩在一起，然后使用初始值进行降维:

def add_edge(graph, edges):
    u, v = edges
    if u != 'null' and v != 'null':
        # ... same thing as before
    return graph

entry = ['A','B','C','null','B','A','D','null','E','F']
graph = reduce(add_edge, zip(entry[:-1], entry[1:]), {})

- slider

---

哇，我甚至不知道reduce是什么。让我去研究一下。但这解决了我的问题。谢谢。 - Eric Klaus

请问您能否将脚本更新为处理单词而非字母？谢谢。 - Eric Klaus

@EricKlaus 我不认为这对单词有任何不同（因为它们也是字符串）。 - slider

Answer 2

借鉴@slider的答案，你也可以使用内置的map（无需导入）来实现此操作：

graph = {}
def add_edge(l):
    u, v = l[0], l[1]
    if u != 'null' and v != 'null':
        if u in graph:
            graph[u][v] = graph[u].get(v, 0) + 1
        else:
            graph[u] = {v: 1}
        if v in graph:
            graph[v][u] = graph[v].get(u, 0) + 1
        else:
            graph[v] = {u: 1}
    return v

list(map(add_edge, [entry[i:i+2] for i in range(len(entry) - 1)]))

>>> graph
{'A': {'B': 2, 'D': 1},
 'B': {'A': 2, 'C': 1},
 'C': {'B': 1},
 'D': {'A': 1},
 'E': {'F': 1},
 'F': {'E': 1}}

使用list(map(func..))的原因是，对于Python 3，map返回一个生成器而不是立即执行，因此必须使用列表强制执行。该行的输出对我们不感兴趣。如果您使用的是Python 2，则可以直接使用map(func..)。

- Rocky Li