그래프
그래프는 모든 것(정점, vertice)에 대한 관계(간선, edge)를 나타내는 자료구조이다.
유향, 무향 그래프
edge의 유형에 따라 유향 그래프, 무향 그래프로 나뉜다.
- 위의 그래프는 edge의 방향이 ORD -> PVD로 명확하다. 이는 유향 그래프이다.
- 아래의 그래프는 edge의 방향이 없다. 이는 무향 그래프이다.
그래프 구현
파이썬에서 그래프를 딕셔너리로 구현할 수 있다.
- 왼쪽의 무향 그래프는 다음과 같이 구현할 수 있다.
graph1 = {1: [2, 3, 5], 2: [1, 3], 3: [1, 2, 4], 4: [3, 5], 5: [1, 4]}- 오른쪽의 무향 그래프는 방향을 신경써야 하기 때문에, 다음과 같이 구현할 수 있다.
graph2 = {1: [2, 3], 2: [3], 3: [4], 4: [], 5: [1, 4]}