グラフの連結性と解法:原因の分析の紹介

深さ優先探索（DFS）:DFSは、スタート地点から始まり、可能な限り深く進んでいく探索方法です。グラフ内のすべての頂点を訪れ、連結成分を特定することができます。

def dfs(graph, start, visited):
    visited.add(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B'],
    'D': ['E'],
    'E': ['D']
}
start_node = 'A'
visited_nodes = dfs(graph, start_node, set())
print(visited_nodes)

幅優先探索（BFS）:BFSは、スタート地点から始まり、隣接する頂点を優先的に訪れる探索方法です。DFSと同様に、グラフ内の連結成分を特定することができます。

from collections import deque
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return visited
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B'],
    'D': ['E'],
    'E': ['D']
}
start_node = 'A'
visited_nodes = bfs(graph, start_node)
print(visited_nodes)

Union-Findアルゴリズム:Union-Findアルゴリズムは、グラフ内の頂点の連結性を効率的に判定するためのデータ構造です。主に、連結成分のマージや連結成分の検索に使用されます。

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):
        x_root = self.find(x)
        y_root = self.find(y)
        if x_root == y_root:
            return
        if self.rank[x_root] < self.rank[y_root]:
            self.parent[x_root] = y_root
        elif self.rank[x_root] > self.rank[y_root]:
            self.parent[y_root] = x_root
        else:
            self.parent[y_root] = x_root
            self.rank[x_root] += 1
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B'],
    'D': ['E'],
    'E': ['D']
# Union-Findアルゴリズムで連結成分を判定する
n = len(graph)
uf = UnionFind(n)
for node in graph:
    for neighbor in graph[node]:
        uf.union(ord(node) - ord('A'), ord(neighbor) - ord('A'))
connected_components = []
for node in graph:
    connected_components.append(uf.find(ord(node) - ord('A')))
print(connected_components)