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

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

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, сложность времени будет такой же.

Я смог в конце концов взломать его. Он работает как для простых графов, так и для структур больших графов. Я ценю тех, кто внес свой вклад в этот вопрос, и особенно в @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