Сделайте уже существующий график полностью подключенным

Question

У меня есть график этой структуры:

G = {
    '1':['100', '134', '1435'], 
    '145':['4', '2345', '253'], 
    '3773':['12'], '773':['1211', '629']}

График на самом деле очень большой, с 6378 узлами и 39932 ребрами. Моя проблема в том, что график отключен, и я хочу, чтобы график был полностью связан без отключенного компонента.

Может кто-нибудь помочь мне с кодом Python, пожалуйста? Я бьюсь головой с воскресенья. Спасибо

def add_disconnected_nodes(Graph, begin):
    gkey = []
    cap_vertices = []
    for vertex in Graph.keys():
        gkey.append(vertex)
    if begin in gkey:
        begin = gkey[0]    
    for vertices in Graph.keys():
        if vertices != begin and vertices not in Graph[begin]:
            cap_vertices.append(vertices)
            #Graph[begin] = [Graph[begin], cap_vertices]
            Graph[begin] + cap_vertices
            Graph.update()
    return Graph

Я написал этот код, но он работал без ошибок. Тем не менее, это не сделает работу. Я знаю, что не делаю что-то правильно

РЕДАКТИРОВАНИЕ: Итак, я переписал код таким образом, теперь он выполняется вечно. Я выбрал начальную вершину в качестве ключа и каждый другой узел узла в значении этого ключа, я пытался добавить к значению. Возможно я делаю что-то не так; Кто-нибудь, пожалуйста, помогите мне!

def add_disconnected_nodes(Graph, begin):
if begin not in Graph:
    return False

beg = {}
bbg = []
for vet in Graph.keys():
    bbg.append(vet)
bba = []
while len(bbg) != 0:
    for ls in bbg:
        if ls != begin and ls not in Graph[begin]:
            bba.append(ls)
            bbg.remove(ls)
            if len(bbg) == 0:
                break
            beg[begin] = Graph[begin] + bba
            Graph.update(beg)
return Graph

Answer 1

Мне удалось в итоге взломать его. Он работает как для простых графов, так и для структур больших графов. Я ценю тех, кто внес свой вклад в этот вопрос, и особенно в @Julien, который заставил меня поверить! Вот мой код ниже:

from collections import defaultdict as dd

def add_disconnected_nodes(Graph, begin):
if begin not in Graph:
    return False

temp_dict = dd()
init_node_list = []
temp_node_list = []
for vertices in Graph.keys():
    init_node_list.append(vertices)

if init_node_list:
    for node_items in init_node_list:
        if node_items != begin and not node_items in Graph[begin]:
            temp_node_list.append(node_items)

    temp_dict[begin] = Graph[begin] + temp_node_list
    init_node_list.remove(node_items)
    Graph.update(temp_dict)

return Graph

Answer 2

Самый простой способ подключить простой граф - это соединить узел со всеми другими узлами графа:

for v in G.keys():
    if v != '1' and '1' not in G[v]:
        G['1'].append(v)
        G[v].append('1')

Здесь мы не использовали DFS или BFS. Код очень прост, но количество добавляемых ребер не минимально. Этот код можно использовать только в простых графах (поскольку определение связности для ориентированных графов отличается).

Временная сложность этого алгоритма составляет O (| V | + | E |) или O (n + m). Если вы используете DFS или BFS, сложность времени будет такой же.