- 그래프란 ?
-
그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.
-
여러 개의 점들이 선으로 이어져 네트워크 망과 비슷한 모습을 가지고 있다.
-
컴퓨터 공학의 그래프는 지하철 노선도, 전기 회로, 도로 교통망, 거미줄 등과 같은 모습과 유사하다.
-
그래프는 트리 그래프와는 달리 루트 노드의 개념이 없고, 사이클이 존재하며, 방향 그래프와 무방향 그래프로 나눌 수 있다. 또한, 부모-자식 관계의 개념이 없다.
- 그래프의 용어
-
정점 (Vertex)
하나의 점을 표현하는 것으로, 그래프의 위치를 나타낸다. 이를 노드라고도 한다. -
간선(Edge)
위치 간의 관계를 선으로 나타낸 것으로, 노드와 노드를 연결하는 선을 뜻한다.
정점 간의 직접적인 관계가 있는 경우 두 점을 잇는 간선이 존재하며, 간접적인 관계의 경우 여러 개의 점과 선에 걸쳐 이어져 있다. -
인접 정점(Adjacent vertex)
하나의 정점에서 간선에 의해 직접적으로 연결되어 있는 정점을 뜻한다. -
가중치 그래프(Weighted Graph)
위치뿐만 아니라 추가적인 정보를 포함한 그래프를 뜻한다. -
차수(degree)
무방향 그래프에서 하나의 정점에 인접한 정점의 수를 뜻한다.
방향 그래프에서는 외부에서 들어오는 간선의 수를 뜻하는 진입 차수(in-degree)와 외부로 향하는 간선의 수를 뜻하는 진출 차수(out-degree)가 있다. -
길이(Length)
정점과 다른 정점의 경로를 구성하는 데 사용된 간선의 수를 뜻한다. -
단순 경로(Simple path)
경로 중에서 반복되는 정점이 없는 경우를 뜻한다. -
사이클(Cycle)
단순 경로의 시작 정점과 끝 정점이 동일한 경우를 말한다.
- 그래프의 특징
-
그래프는 네트워크 모델을 표현한 것으로 노드와 노드 사이의 관계를 위치로 표현한 것이다.
-
그래프를 순회하기 위해 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 사용해야 한다.
-
트리와는 달리 부모-자식 관계가 없고, 루트 노드가 존재하지 않는다.
-
방향 그래프와 무방향 그래프가 존재한다.
-
노드는 간선이 여러 개 존재할 수 있으며, 없을 수도 있다.
- 그래프의 표현 방식
- 인접 행렬
두 정점을 직접적으로 이어주는 간선이 있을 때, 이 두 정점은 인접하다고 표현할 수 있다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 표현한다.
정점끼리 인접한 경우 1(true), 인접하지 않는 경우를 0(false)으로 나타낼 수 있으며, 가중치 그래프라면 1 대신 의미 있는 값을 저장한다.
인접 행렬은 두 정점 사이에 관계가 있는지 없는지를 판단하기 위해 사용하며, 가장 빠른 경로(Shortest path)를 찾고자 할 때 사용한다.
- 인접 리스트
인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한 것이다. 정점마다 하나의 리스트를 가지고 있으며, 자신과 인접한 다른 정점의 정보를 담고 있다.
인접 리스트는 정점 별로 우선순위를 고려하여 구현할 수 있으며, 메모리를 효율적으로 사용하고자 할 때 주로 사용된다. 인접 행렬은 인접 리스트와는 달리 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하기 때문이다.
