그래프에서 특정 노드로부터 도달할 수 있는 모든 노드를 찾아야 하는 경우, 너비 우선 탐색(BFS, Breadth-First Search) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 간선(edge)을 추가하는 함수, BFS를 수행하는 함수, 도달 가능한 노드를 출력하는 함수 등을 각각 정의한 뒤 이를 조합하면, 여러 시작 노드에 대해 각각 도달 가능한 노드 집합을 손쉽게 구할 수 있습니다.
아래는 이를 구현한 예제입니다.
예제
from collections import deque
def add_edge(v, w):
global visited_node, adj
adj[v].append(w)
adj[w].append(v)
def BFS_operation(component_num, src):
global visited_node, adj
queue = deque()
queue.append(src)
visited_node[src] = 1
reachableNodes = []
while (len(queue) > 0):
u = queue.popleft()
reachableNodes.append(u)
for itr in adj[u]:
if (visited_node[itr] == 0):
visited_node[itr] = 1
queue.append(itr)
return reachableNodes
def displayReachableNodes(m):
for i in m:
print(i, end = " ")
print()
def findReachableNodes(my_list, n):
global V, adj, visited_node
a = []
component_num = 0
for i in range(n):
u = my_list[i]
if (visited_node[u] == 0):
component_num += 1
a = BFS_operation(component_num, u)
print("The reachable nodes from ", u, " are")
displayReachableNodes(a)
V = 7
adj = [[] for i in range(V + 1)]
visited_node = [0 for i in range(V + 1)]
add_edge(1, 2)
add_edge(2, 3)
add_edge(3, 4)
add_edge(3, 1)
add_edge(5, 6)
add_edge(5, 7)
my_list = [ 2, 4, 5, 7 ]
arr_len = len(my_list)
findReachableNodes(my_list, arr_len)
출력
The reachable nodes from 2 are 2 1 3 4 The reachable nodes from 4 are 2 1 3 4 The reachable nodes from 5 are 5 6 7 The reachable nodes from 7 are 5 6 7
코드 설명
필요한 패키지를 가져옵니다. 여기서는 큐 자료구조를 위해
collections모듈의deque를 사용합니다.add_edge함수는 인접 리스트(adjacency list) 형태의 그래프에 두 노드 사이의 간선을 추가합니다.BFS_operation함수는 deque를 활용해 너비 우선 탐색 방식으로 그래프를 순회하며, 시작 노드에서 도달할 수 있는 모든 노드를 리스트로 반환합니다.displayReachableNodes함수는 전달받은 노드 목록을 공백으로 구분하여 콘솔에 출력합니다.findReachableNodes함수는 주어진 노드 목록을 순회하면서, 아직 방문하지 않은 노드에 대해BFS_operation을 호출합니다.add_edge함수를 통해 그래프에 간선들이 차례대로 추가됩니다.탐색을 시작할 노드들의 리스트가 정의됩니다.
함수가 호출되고, 각 시작 노드별 도달 가능한 노드 목록이 콘솔에 출력됩니다.
결과 분석
노드 2와 4는 같은 연결 요소(connected component)에 속해 있으므로, 두 노드에서 도달 가능한 노드 집합은 동일하게 {1, 2, 3, 4}입니다. 마찬가지로 노드 5와 7도 같은 연결 요소에 속해 있어 {5, 6, 7}이 출력됩니다. 이처럼 BFS는 시작 노드에서 간선으로 연결된 모든 노드를 레벨(level) 단위로 탐색하기 때문에, 도달 가능한 노드를 빠짐없이 찾아내는 데 매우 유용한 알고리즘입니다.