我有一组节点(N=7)
{a, b, c, d, e, f, g}
这些节点组成一个或多个不同的无向图,我想找到节点数最多的图。但是,我有一个限制,即复杂度不能超过 (N*M),其中 M 是单个节点具有的最大边数(具有最大边的节点)。这是节点结构的示例
nodes = {a: [b], b: [a, c], c: [b], d:[e, f], e: [d, f], f:[e, d, g], g:[f]}
在这个例子中,我们有两个无向图 1. {a, b, c} 和 2. {d, e, f, g}。所以答案应该是 4。
对于每个节点我都可以进行图遍历,例如dfs或bfs,而这只有O(V+E)的复杂度(V图中的节点数和E图中的边数)。如果像上面这样的节点集中有多个不同的无向图(我直到运行后才知道),就会出现问题。我将不得不遍历节点集中的每个节点,执行导致 O(N*(V+E)) 的 dfs,这不满足时间复杂度约束。我想一旦我在第一个图上执行了 dfs,我就可以从我们正在循环的 N 个节点集中删除它的节点(因此将循环从 N 减少到其他东西)但我不确定这如何影响时间复杂度数学上?以下是我目前正在使用的代码,如有任何建议,我们将不胜感激。我可能把这个复杂化了......
def dfs(node_set, n, vis):
if n not in vis:
vis.add(n)
for n in node_set[n]:
getDfs(node_set,n,vis)
return visited
graphs = []
for n in nodes:
graphs.append(getSets(nodes, n, set()))
nums = []
for g in graphs:
nums.append(len(g))
max_num = max(nums)
>> 4
最佳答案
下面的方法遍历每个顶点及其边,以在每个图中找到完整的顶点集。您还必须遍历图的数量以找到跨图的最大顶点数。
def findgraphs(nodes):
graphs = []
while nodes:
graph = set()
queue = set([next(iter(nodes))])
while queue:
nextq = set()
graph.update(queue)
for q in queue:
nextq.update(n for n in nodes[q] if n not in graph)
del nodes[q]
queue = nextq
graphs.append(graph)
return graphs
nodes = {'a': ['b'], 'b': ['a', 'c'], 'c': ['b'], 'd': ['e', 'f'], 'e': ['d', 'f'], 'f': ['e', 'd', 'g'], 'g': ['f']}
graphs = findgraphs(nodes)
m = max(len(g) for g in graphs)
print(m)
# 4
关于python - 在无向图中查找最大节点数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/58097405/