python - 将社区结构(列表)转换为邻接表

Question

给定社区结构(列表的列表):

[[A,B,C], [B,D,E,G], [A,C,F,H],[F,K, H]]

假设每条边的权重为 1，在子组内是无向的。

我想通过对每个人应用广度/深度优先搜索来找到最有影响力的人，他与 G、F(边的最小和)有最短的联系。

广度优先搜索的通用代码如下:

def bfs_paths(graph, start, goal):
    queue = [(start, [start])]
    while queue:
        (vertex, path) = queue.pop(0)
        for next in graph[vertex] - set(path):
            if next == goal:
                yield path + [next]
            else:
                queue.append((next, path + [next]))

问题是“图”应该表示为邻接表。例如:

graph = {'A': set(['B', 'C', 'F', 'H']),
         'B': set(['D', 'E','G']),
         'C': set(['A', 'F', 'H']),
         'D': set(['B', 'E', 'G' ]),
         'E': set(['B', 'D', 'G' ]),
         'F': set(['K', 'H']),
         'G': set(['B', 'D', 'E'])
         'H': set(['K', 'F']}

主要问题:如何将社区结构(列表)转换为邻接表？

附带问题:还有其他合适的算法吗？

Edit1:我试过按照这个 stackoverflow post .但我坚持改进代码以满足预期结果

Answer 1

假设所有社区都完全连接，您可以通过遍历组并使用 setdefault 在需要的地方创建新条目并添加节点来相当快速地转换为邻接列表:

community = [['A','B','C'], ['B','D','E','G'], ['A','C','F','H'],['F','K','H']]

adj_list = {}

for group in community:
    for member in group:
        adj_list.setdefault(member, set()).update((set(group) - {member}))

adj_list 将是:

{'A': {'B', 'C', 'F', 'H'},
 'B': {'A', 'C', 'D', 'E', 'G'},
 'C': {'A', 'B', 'F', 'H'},
 'D': {'B', 'E', 'G'},
 'E': {'B', 'D', 'G'},
 'G': {'B', 'D', 'E'},
 'F': {'A', 'C', 'H', 'K'},
 'H': {'A', 'C', 'F', 'K'},
 'K': {'F', 'H'}}

另一种方法是使用 defaultdict(set)，然后您只需对其进行索引并以类似的方式进行更新。