그래프 기본 - 그래프를 코드로 표현하기

https://gliver.tistory.com/35

그래프 종류

• 방향 그래프

  • 간선의 방향이 한 방향으로 정해져 있는 그래프

  

• 양방향 그래프

  • 간선의 방향이 양방향인 그래프

  

• 가중 그래프

  • 간선에 가중치가 존재하는 그래프

  

그래프를 코드로 표현하는 방법 3가지

1. 인접 리스트 (Adjacency List)
   • 각 노드를 기준으로 연결된 노드를 저장하는 방식

adj_list = [[] for _ in range(4)]

adj_list[0].append(1); adj_list[0].append(2)
adj_list[1].append(3)
adj_list[2].append(3)
adj_list[3].append(0)

print(adj_list)

2. 인접 행렬 (Adjacency Matrix)
   • (노드의 개수) x (노드의 개수) 형태의 행렬을 만든 후에 간선을 표현하는 방식

adj_matrix = [[0 for _ in range(4)] for _ in range(4)]

adj_matrix[0][1] = 1; adj_matrix[0][2] = 1
adj_matrix[1][3] = 1
adj_matrix[2][3] = 1
adj_matrix[3][0] = 1

print(adj_matrix)

3. 간선 리스트 (Edge List)
   • 간선의 정보만을 간단히 표현하는 방식으로, 간선 1개당 노드 2개로 표현하는 방식

edge_list = []

edge_list.append([0, 1])
edge_list.append([0, 2])
edge_list.append([1, 3])
edge_list.append([2, 3])
edge_list.append([3, 0])

print(edge_list)

내용 정리

• 인접 리스트
  • 그래프를 코드로 표현할 때 이 방법을 기본(default)로 생각하면 된다.
    • 어떤 노드와 연결된 노드들을 쉽게 접근할 수 있다.
    • 따라서, 그래프 순회(탐색)에 사용하기에 적합한 형식이다.
  • 최단 경로 알고리즘의 다익스트라 알고리즘을 구현할 때에 쓰인다.
• 인접 행렬
  • 어떤 노드 A에서 B로 가는 간선을 확인해야 하는 작업이 많은 경우에 사용하면 된다.
    • adj_matrix[A][B] 를 접근하면 되기 때문에 $O(1)$에 확인할 수 있다.
  • 최단 경로 알고리즘의 플로이드 워셜 알고리즘을 구현할 때에 쓰인다.
• 간선 리스트
  • 간선들을 기준으로 무언가를 처리해야할 때 사용하면 된다.
  • 최단 경로 알고리즘의 벨만-포드를 구현할 때에 쓰인다.