[Python] Graph 종류 및 구현

그래프 구성

• 노드(node)
• 간선(edge)

그래프 종류

무방향 그래프 vs 방향 그래프

• 무방향 그래프: 간선을 통해 양방향으로 갈 수 있다
• 방향 그래프: 간선에 방향성이 존재

연결 그래프 vs 비연결 그래프

• 연결 그래프: 무방향 그래프에 있는 모든 정점 쌍에 대해서 항상 경로가 존재하는 경우
• 비연결 그래프: 무방향 그래프에서 특정 정점쌍 사이에 경로가 존재하지 않는 경우

사이클 vs 비순환 그래프

• 사이클: 단순 경로의 시작 정점과 종료 정점이 동일한 경우
  • 단순 경로: 경로 중에서 반복되는 정점이 없는 경우
• 비순환 그래프: 사이클이 없는 그래프

완전 그래프

• 그래프에 속해있는 모든 정점이 서로 연결되어 있는 그래프

그래프 구현 방법 - 2차원 리스트

1. 인접행렬: 2차원 배열로 그래프의 연결 관계를 표현

################
   0  1  2
0  0  8  9
1  8  0  INF
2  9  INF 0
################
INF = 99999999
graph = [
	[0, 8, 9],
	[8, 0, INF],
	[9, INF, 0]
]

2. 인접리스트: 리스트로 그래프의 연결 관게를 표현

################
[[(1,8), (2,9)], [(0,8)], [(0,9)]]
################
graph = [[] for _ in range(3)]
graph[0].append((1, 8))
graph[0].append((2, 9))
graph[1].append((0, 8))
graph[2].append((0, 9))