[자료구조] 그래프(Graph)

🔻그래프(Graph)란?

 그래프는 정점(Vertex)과 그 사이를 잇는 간선(Edge)로 이루어져 있다. 즉 정점들 사이의 관계를 나타내는 자료구조이다. G = (V,E)의 형식으로 정의하는데 여기서 V는 정점, E는 간선을 의미한다. 그래프의 대표적인 예시는 지하철 노선도를 들 수 있을 것 이다. 지하철 역과 그 사이의 노선을 표현하는 지하철 노선도는 대표적인 그래프의 예시라고 할 수 있다.

 

🔸그래프의 종류

무방향 그래프(Undirected graph)

 간선에 방향성이 포함되어 있지 않은 그래프이다. 그림에서 A와 B를 연결하는 간선을 (A, B)라고 하면, (A,B)와 (B,A)는 서로 같은 간선이다. 

정점이 n개라할때 무방향 그래프가 가질 수 있는 최대의 간선 개수는 n(n-1)/2개 이다.

출처 : https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c

 

방향 그래프(Directed graph)

 말 그대로 간선에 방향성이 포함되어 있는 그래프이다. 그림에서 A에서 B로가는 간선을 (A, B)라고 하면, 이 간선은 A에서 B로만 갈 수 있고 그 반대는 불가능하다. (A,B)와 (B,A)는 서로 다른 간선이다. 방향그래프를 digraph라고도 한다.

정점이 n개라할때 무방향 그래프가 가질 수 있는 최대의 간선 개수는 n(n-1)개 이다.

출처 : https://www.zerocho.com/category/Algorithm/post/584b9033580277001862f16c

완전 그래프(Complete graph)

한 정점에서 모든 다른 정점과 연결되어 최대의 간선수를 가지는 그래프이다.

https://itdexter.tistory.com/84

 

 

가중치 그래프(Weighted graph)

 간선에 비용이나 가중치를 포함하고 있는 그래프이다.

출처 : https://codepumpkin.com/graph/

 

[그래프에서 사용되는 용어들]

정점(Vertex) : 그래프에 저장하고 있는 객체

간선(Edge) : 정점들 사이를 잇는 선

차수(Degree) : 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입/진출 차수의 합

진입차수(In-Degree) : 방향 그래프에서 정점으로 들어오는 간선의 수

진출차수(Out-Degree) : 방향 그래프에서 정점에서 나가는 간선의 수

사이클(Cycle) : 경로의 시작 정점과 마지막 정점이 같은 경로

인접 정점(adjacent vertex): 한 정점에서 간선을 통하여 갈 수 있는 다른 정점

 

 

 

🔸그래프의 표현

 이러한 그래프를 표현할 수 있는 방법은 크게 인접행렬로 표현하는 방법, 리스트로 표현하는 방법 두가지가 존재한다.

인접행렬

 

 이러한 5개의 정점을 가지는 그래프를 5x5 행렬로 표현하면 이렇게 표현할 수 있을 것이다. 무방향 그래프라면 행렬은 대각선 대칭을 이룬다. 

방향 그래프를 행렬로 나타내면 이런 식으로 표현 할 수 있다.

 

그래프 자료구조를 행렬로 표현하면 다음과 같은 특성을 가진다.

• n^2bit의 크기를 차지한다. (무방향 그래프에서는 어차피 대칭이므로 (n-1)n/2 bit만으로도 표현 가능하다.)
• 정점의 차수 또는 인접한 정점들을 찾을 대에 O(n)의 시간 복잡도를 가진다.

리스트

정점마다 1개의 배열을 가지며 그 배열에는 그 정점과 인접한 정점들의 정보가 들어간다.

리스트를 사용할 때는 또 두개로 나눌 수 있는데 Linked List를 사용할 떄와 Array를 사용할 때이다.

Linked List

Array

 

 

🔸리스트 vs 행렬

 그렇다면 리스트와 행렬중에 어느 방식을 채택해서 그래프를 구성하는 것이 효율적일까?

 먼저 행렬을 사용할 경우 리스트를 사용하는 방식보다 공간적으로 소모가 더 크다. 하지만 연결된 정접들을 찾는 연산속도가 더 빠르다. 그 이유는 행렬은 이중배열속에서 바로 연결 유무를 파악할 수 있지만, 리스트로 구현할 경우 연결되어 있는지를 확인하려면 해당 정점의 엣지정보를 모두 탐색해야하기 때문이다.

 만약 정점들 사이의 연결이 많이 없다면 리스트를 써서 그래프를 구성하는 것이 공간을 아낄 수 있다. 하지만 정점사이의 연결이 많다면 행렬을 써서 성능을 높이는게 좋다.

 하지만 공간을 조금더 쓰더라도 성능을 높이는 쪽이 더 좋을 것 같다는 생각이 든다. 따라서 공간의 제약이 심한 경우가 아니라면 행렬을 이용하여 구현하는 것이 좋을 것 같다.

 

 

 

🔻그래프 탐색 알고리즘 : DFS와 BFS

그래프 탐색 알고리즘이란 한 정점에서 시작하여 차례대로 그래프에 있는 모든 정점들은 한번씩 방문하는 알고리즘을 뜻한다.  깊이 우선 탐색(DFS - Depth-First Search)와 너비 우선 탐색(BFS - Breadth-First Search) 두가지의 알고리즘이 존재한다. 

위 그림을 보면 어떤 느낌인지 감이 올 것이다. 위 사진대로 DFS는 깊이를 우선으로 즉, 세로로 한줄씩 탐색을 해나가는 것이고, BFS는 너비를 우선으로 즉, 가로로 한줄씩 탐색을 해나가는 알고리즘이라고 생각하면 된다. DFS와 BFS알고리즘 같은 경우에는 굉장히 중요한 알고리즘중에 하나이므로 잘 이해하는 것이 중요하다.

 

DFS와 BFS에 대해 자세하게 내용을 다루고 싶어서 따로 글을 분리하였다. 자세한 설명은 아래 포스트에 기술되어 있다.

깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)

간단히 정리하자면, DFS는 재귀함수또는 스택을 사용하여 구현, BFS는 큐를 사용하여 구현한다. 또한 DFS와 BFS의 시간복잡도는 동일하다. 인접 행렬을 사용하여 구현한 그래프에서는 O(n^2), 인접 리스트를 사용하여 구현한 그래프에서는 O(n+e)의 시간복잡도를 가진다. (n = 정점의 개수, e = 간선의 개수)