무방향 그래프(Undirected Graph)에서 깊이 우선 탐색(Depth First Search, DFS)을 이용해 모든 연결 요소를 찾아야 하는 경우가 있습니다. 이때는 초기값 설정, DFS 순회 수행, 연결 요소 탐색, 그래프에 노드 추가 등의 기능을 담은 메서드들을 포함하는 클래스를 정의하면 됩니다. 클래스의 인스턴스를 생성한 뒤 해당 메서드들을 호출하여 원하는 연산을 수행할 수 있습니다.
아래는 이를 구현한 예시입니다.
예제 코드
class Graph_struct:
def __init__(self, V):
self.V = V
self.adj = [[] for i in range(V)]
def DFS_Utililty(self, temp, v, visited):
visited[v] = True
temp.append(v)
for i in self.adj[v]:
if visited[i] == False:
temp = self.DFS_Utililty(temp, i, visited)
return temp
def add_edge(self, v, w):
self.adj[v].append(w)
self.adj[w].append(v)
def connected_components(self):
visited = []
conn_compnent = []
for i in range(self.V):
visited.append(False)
for v in range(self.V):
if visited[v] == False:
temp = []
conn_compnent.append(self.DFS_Utililty(temp, v, visited))
return conn_compnent
my_instance = Graph_struct(5)
my_instance.add_edge(1, 0)
my_instance.add_edge(2, 3)
my_instance.add_edge(3, 0)
print("1-->0")
print("2-->3")
print("3-->0")
conn_comp = my_instance.connected_components()
print("The connected components are :")
print(conn_comp)실행 결과
1-->0 2-->3 3-->0 The connected components are : [[0, 1, 3, 2], [4]]
코드 설명
'Graph_struct'라는 이름의 클래스를 정의합니다.
'add_edge' 메서드는 그래프에 간선(엣지)을 추가하는 역할을 합니다. 무방향 그래프이므로 양방향으로 인접 리스트에 추가됩니다.
'DFS_Utility' 메서드는 깊이 우선 탐색 방식으로 그래프를 순회하며, 방문한 노드들을 임시 리스트에 저장합니다.
'connected_components' 메서드는 서로 연결되어 있는 노드들의 집합, 즉 연결 요소를 판별하는 역할을 합니다.
클래스의 인스턴스를 생성하고, 이를 통해 메서드들을 호출합니다.
그래프에 추가된 노드와 간선 정보가 콘솔에 출력됩니다.
마지막으로 탐색 결과인 연결 요소들이 콘솔에 출력됩니다. 실행 결과 [[0, 1, 3, 2], [4]]에서 볼 수 있듯이, 노드 0, 1, 2, 3은 하나의 연결 요소를 이루고 노드 4는 다른 어떤 노드와도 연결되어 있지 않으므로 독립적인 연결 요소로 분류됩니다.