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

[14강] 그래프(Graph) 기본

안녕하세요 Gliver 입니다. 이번 글에서는 그래프(Graph) 기본에 대해 알아보겠습니다. 목차 그래프를 코드로 표현하기 인접 리스트 (Adjacency List) 인접 행렬 (Adjacency Matrix) 간선 리스트 (Edge List) 정리 지난 글에서 그래프는 노드(정점)와 간선으로 이루어져 있다고 설명하였습니다. 이번 글에서는 이러한 그래프를 어떻게 코드로 표현할 수 있는지 알아봅시다. 그래프를 코드로 표현하기 그래프를 코드로 어떻게 표현할 수 있을까? 그래프는 노드와 간선으로 구성되어 있으므로 노드와 간선을 각각 어떻게 표현할 수 있는지 살펴보자. 노드는 하나의 정점으로 노드의 개수만큼의 공간으로 표현할 수 있다. 간선은 노드와 노드를 선을 잇는 것이므로 간선 1개는 노드 2개로 표현할 ..

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개로 생각하면 된다.
 
• 가중 그래프인 경우에는 (연결된 노드, 간선의 가중치) 형태로 저장하면 된다.
 

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)
 
• 양방향 그래프인 경우에는 하나의 간선을 간선 2개로 생각하면 된다.
 
• 가중 그래프인 경우에는 간선이 존재하는 경우 1이 아닌 가중치를 저장하면 된다.
 

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)
 
• 양방향 그래프인 경우에는 하나의 간선을 간선 2개로 생각하면 된다.
 
• 가중 그래프인 경우에는 (노드 A, 노드 B, 간선의 가중치) 형태로 저장하면 된다.

내용 정리

• 인접 리스트
• 그래프를 코드로 표현할 때 이 방법을 기본(default)로 생각하면 된다.
• 어떤 노드와 연결된 노드들을 쉽게 접근할 수 있다.
• 따라서, 그래프 순회(탐색)에 사용하기에 적합한 형식이다.
• 최단 경로 알고리즘의 다익스트라 알고리즘을 구현할 때에 쓰인다.

• 인접 행렬
• 어떤 노드 A에서 B로 가는 간선을 확인해야 하는 작업이 많은 경우에 사용하면 된다.
• adj_matrix[A][B] 를 접근하면 되기 때문에 에 확인할 수 있다.
• 최단 경로 알고리즘의 플로이드 워셜 알고리즘을 구현할 때에 쓰인다.

• 간선 리스트
• 간선들을 기준으로 무언가를 처리해야할 때 사용하면 된다.
• 최단 경로 알고리즘의 벨만-포드를 구현할 때에 쓰인다.