[알고리즘] 그래프

그래프 : Graph

DFS나 BFS는 모두 그래프 순회 알고리즘, 그래프 탐색 알고리즘이다. 그렇다면 그래프에 대해서 자세히 짚고 넘어가자.

우선 알고리즘에서의 그래프는 우리가 흔히 사용했던 막대그래프나 주식그래프 같은 형태가 아니다.

 

나의 블로그 방문 그래프

 

그래프는 노드(Node)와 간선(Edge)으로 표현되며 이때 노드를 정점(Vertex)이라고도 말한다.

그래프 구조

 

노드와 노드가 간선으로 연결되어 있다면 두 노드는 인접해있다고 한다. 그래프 탐색은 하나의 노드를 시작으로 인접한 노드를 방문하는 것을 말한다. 

그래프를 표현하는 방법은 크게 두가지가 있다.

 

• 인접 행렬 (Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식
• 인접 리스트 (Adjacency List) : 리스트로 그래프의 연결 관계를 표현하는 방식

 

그래프 예시

 

위 그래프를 인접 행렬로서 정리한 표이다. 행은 현재 노드를 의미하고 열은 가고자하는 노드를 말한다. 그리고 그 값은 간선을 의미한다.

	0	1	2
0	0	7	5
1	7	0	무한
2	5	무한	0

 

아래의 그림은 인접 리스트 방식으로 저장한 것이다.

인접 리스트

인접 리스트와 인접 행렬은 서로 장단점이 있다. 인접 행렬은 연결되어 있지 않은 간선의 값도 무한이라고 저장해놓기에 메모리 낭비가 있다. 반면에 인접 리스트는 필요한 값들만 저장하기 때문에 그런 메모리 낭비는 없는 편이다. 반대로 특정 간선을 찾을 때, 즉 두 노드가 연결되어 있는지 파악할 때에는 인접 행렬이 더 효율적이다. 

 

 

이것이 코딩 테스트다 with 파이썬를 읽고 정리한 글입니다.