Algorithm | 자료구조 : Graph

Graph ?

 그래프(Graph)는 노드(N, Node)와 그 노드를 연결하는 간선(E, Edge)을 통해 정점간의 관계를 표현하는 자료구조이다. 일상 생활 속 지도나 지하철 노선도를 그래프라고 할 수 있다. 지도 어플에서 지점 간 최단 거리를 찾는 과정은 그래프를 탐색하는 과정이라 볼 수 있다.

 

그래프 표현              출처 https://manducku.tistory.com/21

Graph 종류

 그래프에서 간선은 방향성이 존재하며 화살표를 이용하여 표현한다. 간선은 순환이 가능하며 자체 간선(Self-loop)도 가능하다. 이러한 간선의 방향성과 순환성으로 그래프의 종류를 나눌 수 있다. 방향성의 유무에 따라 방향 그래프(Directed)와 무방향 그래프(Undirected)로, 순환성의 유무에 따라 순환 그래프(Cyclic)와 비순환 그래프(Acyclic)로 나뉜다.

 

가중치 그래프    출처 https://manducku.tistory.com/21

 간선에 가중치가 있는 그래프도 있다. 정점간에 이동 거리가 간선에 추가되면 최단 거리를 찾는 과정은 정점을 거치는 횟수 뿐만 아니라 가중치까지 고려해주어야 한다.

Graph 구현

그래프를 구현하는 방법은 인접 행렬을 이용한 방법과 인접 리스트를 이용한 방법이 있다.

 

인접 리스트(Adjacency List)

출처 https://manducku.tistory.com/21

 인접 리스트는 N개의 공간에 각 정점에 간선으로 연결된 정점을 연결 리스트 방식으로 추가하며 구현하는 방식이다. 노드의 갯수가 N인 그래프를 인접 리스트로 구현하려면 N개의 공간에 실제 간선 만큼 원소가 들어 있으므로 N + E개의 공간을 필요로 한다.

 

인접 행렬(Adjacency Matrix)

출처 https://manducku.tistory.com/21

 인접 행렬은 N x N 행렬에 연결 유무에 따라 연결 되었으면 1, 연결이 되지 않았으면 0으로 표현하여 구현하는 방식이다. 노드의 갯수가 N인 그래프를 인접 행렬로 구현하려면 N x N개의 공간을 필요로 한다. 

---

Reference

 

· 그래프의 개념과 BFS, DFS - https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html

· 그래프에 대해서 - https://www.youtube.com/watch?v=fVcKN42YXXI

· 그래프의 정의와 표현 - https://manducku.tistory.com/21