给定的社区结构(列表列表):
[[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']}
主要问题:如何将社区结构(列表)转换为邻接列表?
附带问题:还有其他合适的算法吗?
编辑1:我尝试遵循此stackoverflow post 。但我坚持改进代码以满足预期结果
最佳答案
假设所有社区都完全连接,您可以通过迭代组并使用 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)
,然后您可以对其进行索引并以类似的方式进行更新。
关于python - 将社区结构(列表)转换为邻接表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56488309/