寻找一组无向图中节点数量的最大值

Question

我有一组节点（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为边数）。问题发生在如果节点集合中有多个不同的无向图就像上面那样（直到运行时我都不知道）。我将必须循环遍历节点集中的每个节点，执行dfs，这会导致O(N*(V+E))的复杂度，这不满足时间复杂度的限制。我猜一旦我对第一个图执行了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

- maracuja

Answer 1

下面的方法遍历每个顶点及其边缘，以找到每个图中的完整顶点集。您还需要遍历图的数量，以找到跨图的最大顶点数。

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

- benvc

---

我认为这个的时间复杂度大于O（N * M）。 - maracuja