비선형 자료구조 - 3. 그래프

그래프 (Graph)

그래프는 정점(Vertex)와 간선(Edge)로 이루어진 순환(Cycle) 형태의 자료구조입니다.

 

트리도 노드와 간선으로 이루어져있는 일종의 그래프이며, 그래프와 트리의 차이점은 순환(Cycle)이 있느냐 없느냐의 차이입니다.

 

이 글에서는 정점과 노드를 같은 뜻으로 사용하도록 하겠습니다.

 

 

그래프의 구조

 

출처 : https://daebaq27.tistory.com/25

• 정점 (Vertext) : 각각의 노드들
• 간선 (Edge) : 노드와 노드를 연결하는 선
• 인접 정점 (Adjacent Vertext) : 간선 하나를 두고 바로 연결된 정점
• 정점의 차수 (Degree) : 무방향 그래프에서 하나의 정점에 인접한 정점의 수
• 진입 차수 (In-degree) : 방향 그래프에서 외부에서 오는 간선의 수
• 진출 차수 (Out-degree) : 방향 그래프에서 외부로 나가는 간선의 수
• 경로 길이 (Path length) : 경로를 구성하는데 사용된 간선의 수
• 단순 경로 (Simple path) : 경로 중에서 반복되는 정점이 없는 경우
• 사이클 (Cycle) :  단순 경로의 시작 정점과 끝 정점이 동일한 경우

 

그래프의 종류

무방향(무향) 그래프

 

간선에 방향이 없는 그래프를 무방향 그래프라고 합니다.

 

양방향으로 이동이 가능하며,  다음 그림과 같이 선분으로 표현합니다. 

 

 

출처  : https://m.blog.naver.com/k97b1114/140163248655

방향이 없고 양방향으로 이동이 가능하기 때문에 간선의 관계 (A, B) = (B, A) 가 성립합니다.

 

방향(유향) 그래프

 

간선에 방향이 있는 그래프를 방향 그래프라고 합니다.

 

정해진 방향으로만 이동이 가능하며, 다음 그림과 같이 화살표로 표현합니다.

 

출처 : https://m.blog.naver.com/k97b1114/140163248655

 

방향이 정해져있기 때문에 간선의 관계 (A, B) ≠ (B, A)가 성립합니다.

 

완전 그래프

 

모든 정점들이 서로 연결되어 있는 그래프를 완전 그래프라고 합니다.

 

출처 : https://m.blog.naver.com/k97b1114/140163248655

 

완전 그래프의 간선 수는 다음과 같습니다.

• 무방향 그래프 : N(N-1) / 2
• 방향 그래프 : N(N-1)

 

가중치 그래프

 

간선에 가중치(Weight)가 할당되어 있는 그래프를 가중치 그래프라고 합니다.

 

출처 : https://m.blog.naver.com/k97b1114/140163248655

 

그래프 탐색

 

그래프의 탐색은 다음과 같은 방식으로 이루어집니다.

DFS (Depth First Search)

 

깊이 우선 탐색으로, 그래프에서 깊은 부분을 우선적으로 탐색하는 방법입니다.

 

 

DFS의 구현

DFS의 경우, Stack이나 재귀 호출을 이용해서 구현합니다.

 

스택으로 구현하는 방법은 다음과 같습니다.

🎢 스택으로 DFS 구현하기
1. 시작 노드를 스택에 삽입하고 방문 처리 합니다.
2. 스택에서 노드 하나를 꺼내 해당 노드의 방문하지 않은 인접 노드들을 스택에 추가하고, 방문처리 합니다.
3. 스택이 빌 때 까지 2번 과정을 반복합니다.

 

BFS (Breadth First Search)

 

너비 우선 탐색으로, 그래프에서 가까운 노드부터 탐색하는 방법입니다.

 

BFS의 구현

 

BFS의 경우, Queue를 이용해서 구현합니다.

 

BFS 구현 방법은 다음과 같습니다.

🚌 Queue로 BFS 구현하기
1. 시작 노드를 큐에 삽입하고 방문 처리 합니다.
2. 큐에서 노드 하나를 꺼내 해당 노드의 방문하지 않는 인접 노드들을 큐에 추가하고, 방문 처리 합니다.
3. 큐가 빌 때 까지 2번 과정을 반복합니다.

 

그래프의 구현

 

인접 행렬 (Adjacency Matrix)

 

2차원 배열을 이용해 그래프를 구현할 수 있습니다.

 

출처 : https://cinux.tistory.com/9

 

배열을 사용하다보니 간선 정보의 확인과 업데이트가 O(1)으로 빠르다는 장점이 있지만, 메모리 공간을 차지 한다는 단점이 있습니다.

 

인접 리스트 (Adjacency List)

 

연결 리스트를 이용해 그래프를 구현할 수 있습니다.

 

출처 : https://cinux.tistory.com/10

 

메모리 사용량이 인접 배열에 비해 상대적으로 적고, 노드의 추가 / 삭제가 빠릅니다. 다만, 간선 정보 확인이 상대적으로 오래 걸립니다.

 

 

인접 행렬 vs 인접 리스트

 

N: 전체 정점 개수 E: 전체 간선 개수	인접 행렬	인접 리스트
특정 간선 검색	O(1)	O(degree(v))
정점 차수 계산	O(N)	O(degree(V))
전체 노드 탐색	O(N^2)	O(E)
메모리	N * N	N + E

 

노드의 개수가 적고 간선이 많으면(밀집 그래프) 인접 행렬을, 노드의 개수가 많고 간선의 수가 적으면(희소 그래프) 인접 리스트를 사용하는 것이 좋습니다.

 

 

참고자료

https://www.youtube.com/watch?v=_hxFgg7TLZQ 

제로베이스 백엔드 스쿨