Python으로 무방향 그래프의 연결 요소 찾기: 깊이 우선 탐색(DFS) 구현 가이드

무방향 그래프에서 연결 요소(Connected Component)란 서로 경로로 이어져 있는 정점들의 집합을 의미합니다. 같은 연결 요소에 속한 두 정점 사이에는 반드시 어떤 경로가 존재하며, 그래프 전체가 몇 개의 독립적인 부분으로 나뉘어 있는지 파악하려면 연결 요소를 찾는 작업이 필요합니다.

연결 요소를 찾으려면 그래프를 표현하는 클래스를 정의하고, 정점 초기화, 간선 추가, 깊이 우선 탐색(DFS) 수행, 연결 요소 탐색 등의 메서드를 함께 구현하면 됩니다. 이후 클래스의 인스턴스를 생성해 각 메서드를 호출하면 원하는 결과를 얻을 수 있습니다.

아래는 이를 구현한 예제입니다.

예제 코드

class Graph_structure:

    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]

    def DFS_Utility(self, temp, v, visited):

        visited[v] = True

        temp.append(v)

        for i in self.adj[v]:
            if visited[i] == False:
                temp = self.DFS_Utility(temp, i, visited)
        return temp

    def add_edge(self, v, w):
        self.adj[v].append(w)
        self.adj[w].append(v)

    def find_connected_components(self):
        visited = []
        connected_comp = []
        for i in range(self.V):
            visited.append(False)
        for v in range(self.V):
            if visited[v] == False:
                temp = []
                connected_comp.append(self.DFS_Utility(temp, v, visited))
        return connected_comp

my_instance = Graph_structure(6)
my_instance.add_edge(1, 0)
my_instance.add_edge(2, 3)
my_instance.add_edge(3, 4)
my_instance.add_edge(5, 0)
print("There are 6 edges. They are : ")
print("1-->0")
print("2-->3")
print("3-->4")
print("5-->0")

connected_comp = my_instance.find_connected_components()
print("The connected components are...")
print(connected_comp)

실행 결과

There are 6 edges. They are :
1-->0
2-->3
3-->4
5-->0
The connected components are...
[[0, 1, 5], [2, 3, 4]]

코드 설명

• Graph_structure라는 이름의 클래스가 정의되며, 생성자 역할을 하는 __init__ 메서드가 포함됩니다. 이 메서드는 정점의 개수(V)를 저장하고 인접 리스트(adj)를 초기화합니다.

• DFS_Utility 메서드는 특정 정점에서 시작해 방문하지 않은 인접 정점을 재귀적으로 따라가며 깊이 우선 탐색(DFS)을 수행하고, 방문한 정점들을 하나의 임시 리스트(temp)에 모아 반환합니다.

• add_edge 메서드는 무방향 그래프의 특성에 맞게 두 정점 v와 w를 서로의 인접 리스트에 추가하여 간선을 연결합니다.

• find_connected_components 메서드는 모든 정점을 순회하면서 아직 방문하지 않은 정점을 발견할 때마다 DFS를 시작하여, 해당 정점과 연결된 모든 정점들을 하나의 연결 요소로 묶습니다.

• 정점이 6개인 Graph_structure 클래스의 인스턴스가 생성됩니다.

• add_edge 메서드를 사용해 1→0, 2→3, 3→4, 5→0의 네 개 간선이 그래프에 추가됩니다.

• 그래프의 간선 정보가 콘솔에 출력됩니다.

• find_connected_components 메서드가 호출되고, 최종적으로 [[0, 1, 5], [2, 3, 4]]라는 두 개의 연결 요소가 콘솔에 표시됩니다.

복잡도 및 참고 사항

이 알고리즘은 각 정점과 간선을 한 번씩만 방문하므로 시간 복잡도는 O(V + E)입니다. 여기서 V는 정점의 수, E는 간선의 수입니다. 또한 너비 우선 탐색(BFS)을 사용해도 동일한 방식으로 연결 요소를 찾을 수 있으며, 이 경우 재귀 호출 대신 큐(queue)를 사용한다는 점만 다릅니다.