Чтобы проверить, связан ли данный граф или нет, с помощью метода поиска в глубину (DFS), можно использовать различные подходы. Вот несколько методов с примерами кода:

Метод 1: рекурсивный DFS

def dfs(graph, start, visited):
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
def is_connected(graph):
    start_node = next(iter(graph))
    visited = set()
    dfs(graph, start_node, visited)
    return len(visited) == len(graph)

В этом методе мы выполняем рекурсивный DFS, начиная с произвольного узла, и отмечаем все посещенные узлы. Если все узлы графа посещены, то граф связен.

Метод 2: итеративный DFS

def is_connected(graph):
    start_node = next(iter(graph))
    visited = set()
    stack = [start_node]
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            stack.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
    return len(visited) == len(graph)

В этом методе мы используем итеративный подход для выполнения DFS. Мы поддерживаем стек, чтобы отслеживать узлы, которые нужно посетить в следующий раз. Мы продолжаем извлекать узлы из стека, пока он не станет пустым. Если все узлы графа посещены, то граф связен.

Метод 3: алгоритм поиска объединения

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_y] = root_x
                self.rank[root_x] += 1
def is_connected(graph):
    nodes = len(graph)
    uf = UnionFind(nodes)
    for node in graph:
        for neighbor in graph[node]:
            uf.union(node, neighbor)
    return len(set(uf.find(i) for i in range(nodes))) == 1

В этом методе мы используем алгоритм Union-Find для определения связности графа. Мы инициализируем структуру данных UnionFind и перебираем каждое ребро графа, выполняя операцию объединения на узлах. Наконец, мы проверяем, принадлежат ли все узлы одному множеству.