Нахождение максимального количества узлов в наборе неориентированных графов - PullRequest
Новая
       71

Нахождение максимального количества узлов в наборе неориентированных графов

3 голосов
/ 25 сентября 2019

У меня есть набор узлов (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

1 Ответ

0 голосов
/ 25 сентября 2019

Подход, описанный ниже, обходит каждую вершину и ее ребра, чтобы найти полный набор вершин в каждом графе.Вам также придется пересмотреть количество графов, чтобы найти максимальное количество вершин в графах. 

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
...