그래프 알고리즘

Python으로 시작하는 네트워크 분석

Eric Ma

Data Carpentry instructor and author of nxviz package

경로 찾기

• 경로 탐색의 활용
  • 최적화: 예) 최단 운송 경로
  • 모델링: 예) 질병 전파, 정보 전달
• 알고리즘: 너비 우선 탐색(BFS)

너비 우선 탐색(BFS)

• 예: 두 노드 간 최단 경로

너비 우선 탐색(BFS)

• 예: 두 노드 간 최단 경로

너비 우선 탐색(BFS)

• 예: 두 노드 간 최단 경로

너비 우선 탐색(BFS)

• 예: 두 노드 간 최단 경로

복습: 이웃 노드

G

<networkx.classes.graph.Graph at 0x10cc08828>

len(G.edges())

57

len(G.nodes())

20

복습: 이웃 노드

list(G.neighbors(1))

[10, 5, 14, 7]

list(G.neighbors(10))

[1, 19, 5, 17, 8, 9, 13, 14]

Let's practice!

Python으로 시작하는 네트워크 분석