[NetworkX] 너비 우선 탐색, 트리 구조 그리기

너비 우선 탐색 Breadth-First Search,  BFS

너비 우선 탐색(Breadth-first search, BFS)은 맹목적 탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. OPEN List는 큐를 사용해야만 레벨 순서대로 접근이 가능하다. (출처: 위키백과)

• 그래프의 한 노드에서 다른 모든 노드까지의 길이를 구하는 (그나마) 효율적인 방법 중 하나

 

아래는 A 노드가 다른 노드들과 얼마나 떨어져있는지 확인하기 위해

너비우선탐색을 진행한 결과입니다.

1. A 본인의 주변 탐색
2. Distance1 : A와 연결되어있는 B, K의 주변 탐색
3. Distance2 : B와 연결되어있는 C, K(하지만 K는 Distance1에 있으므로 생략)
4. Distance3 : C와 연결되어있는 E, F, B(B는 Distance2에 있으므로 생략)
5. ....

 

NetworkX를 활용하면 코드 한줄로 너비우선탐색 트리를 쉽게 생성할 수 있습니다.

 

 

특정 노드 기준으로 BFS 트리구조 만들기

먼저 위의그래프를 만들어 주겠습니다.

import networkx as nx

edges = [('A','B'),('A','K'),('B','C'),('B','K'),('C','E'),('C','F'),
         ('D','E'),('E','F'),('E','H'),('F','G'),('E','I'),('I','J')]

G = nx.Graph()
G.add_edges_from(edges)

 

BFS 그래프 생성하기

이제 A노드를 기준으로 BFS를 해봅시다.

# BFS
T = nx.bfs_tree(G,'A')

# 결과 확인하기
T.edges()
# OutEdgeView([('A', 'B'), ('A', 'K'), ('B', 'C'), ('C', 'E'), ('C', 'F'), 
#              ('E', 'D'), ('E', 'H'), ('E', 'I'), ('F', 'G'), ('I', 'J')])

 

BFS 트리구조 plot 그리기

edges()로 보는건 눈에 잘 안들어 오니까 그림을 그려 확인합시다

from networkx.drawing.nx_pydot import graphviz_layout

pos = graphviz_layout(T, prog='dot')
nx.draw(T, pos, with_labels=True)

 

가장 짧은 경로의 길이

nx.shortest_path_length(G,'A')

# 결과
{'A': 0,
 'B': 1,
 'K': 1,
 'C': 2,
 'F': 3,
 'E': 3,
 'G': 4,
 'H': 4,
 'I': 4,
 'D': 4,
 'J': 5}