[CS] 그래프(Graph)란 무엇인가?

그래프 (Graph)

그래프는 여러 개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조이다.

컴퓨터 공학에서 사용하는 그래프는 X축과 Y축의 값을 나타내는 그래프와는 다른 모습을 가지고 있다. 여러 개의 점들이 선으로 이어져 네트워크 망과 비슷한 모습을 가지고 있다. 컴퓨터 공학의 그래프는 지하철 노선도, 전기 회로, 도로 교통망, 거미줄 등과 같은 모습과 유사하다.

 

그래프는 트리 그래프와는 달리 루트 노드의 개념이 없고, 사이클이 존재하며, 방향 그래프와 무방향 그래프로 나눌 수 있다. 또한, 부모-자식 관계의 개념이 없다.

 

그래프의 용어

정점 (Vertex)

하나의 점을 표현하는 것으로, 그래프의 위치를 나타낸다. 이를 노드라고도 한다.

 

간선(Edge)

위치 간의 관계를 선으로 나타낸 것으로, 노드와 노드를 연결하는 선을 뜻한다.

정점 간의 직접적인 관계가 있는 경우 두 점을 잇는 간선이 존재하며, 간접적인 관계의 경우 여러 개의 점과 선에 걸쳐 이어져 있다.

 

인접 정점(Adjacent vertex)

하나의 정점에서 간선에 의해 직접적으로 연결되어 있는 정점을 뜻한다.

 

가중치 그래프(Weighted Graph)

위치뿐만 아니라 추가적인 정보를 포함한 그래프를 뜻한다.

 

차수(degree)

무방향 그래프에서 하나의 정점에 인접한 정점의 수를 뜻한다.

방향 그래프에서는

외부에서 들어오는 간선의 수를 뜻하는 진입 차수(in-degree)와

외부로 향하는 간선의 수를 뜻하는 진출 차수(out-degree)가 있다.

 

길이(Length)

정점과 다른 정점의 경로를 구성하는 데 사용된 간선의 수를 뜻한다.

 

단순 경로(Simple path)

경로 중에서 반복되는 정점이 없는 경우를 뜻한다.

 

사이클(Cycle)

단순 경로의 시작 정점과 끝 정점이 동일한 경우를 말한다.

 

그래프의 특징

1. 그래프는 네트워크 모델을 표현한 것으로 노드와 노드 사이의 관계를 위치로 표현한 것이다.
2. 그래프를 순회하기 위해 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)을 사용해야 한다.
3. 트리와는 달리 부모-자식 관계가 없고, 루트 노드가 존재하지 않는다.
4. 방향 그래프와 무방향 그래프가 존재한다.
5. 노드는 간선이 여러 개 존재할 수 있으며, 없을 수도 있다.

 

그래프의 표현 방식

인접 행렬

두 정점을 직접적으로 이어주는 간선이 있을 때, 이 두 정점은 인접하다고 표현할 수 있다. 인접 행렬은 서로 다른 정점들이 인접한 상태인지를 표시한 행렬로 2차원 배열의 형태로 표현한다.

 

정점끼리 인접한 경우 1(true), 인접하지 않는 경우를 0(false)으로 나타낼 수 있으며, 가중치 그래프라면 1 대신 의미 있는 값을 저장한다.

 

인접 행렬은 두 정점 사이에 관계가 있는지 없는지를 판단하기 위해 사용하며, 가장 빠른 경로(Shortest path)를 찾고자 할 때 사용한다.

 

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태로 표현한 것이다. 정점마다 하나의 리스트를 가지고 있으며, 자신과 인접한 다른 정점의 정보를 담고 있다.

 

인접 리스트는 정점 별로 우선순위를 고려하여 구현할 수 있으며, 메모리를 효율적으로 사용하고자 할 때 주로 사용된다. 인접 행렬은 인접 리스트와는 달리 모든 경우의 수를 저장하기 때문에 상대적으로 메모리를 많이 차지하기 때문이다.