[자료구조] 그래프란? 개념과 표현 방법

728x90

그래프란?

그래프란 노드와 간선의 집합으로 정의되며, 알고리즘에서 노드(Node)와 노드를 연결하는 간선(Edge)로 구성된 자료구조를 말한다.

이때 간선은 노드 쌍을 연결하며, 경우에 따라 가중치(Weight) 정보가 포함될 수 있다.

특히, 그래프는 선형 자료구조나 트리 자료구조로 표현하기 어려운 N : N 관계를 가지는 원소들을 표현하기에 용이하다.

어디에서 많이 쓰일까?

그래프는 네트워크 모델링에 아주 유용하게 사용된다.

예를 들어, 소셜 네트워크 분석, 지하쳘 통행 분석, 최단 경로 문제와 같은 것을 해결하는 데 사용될 수 있다.

그래프의 용어

정점 (Vertex)

→ 그래프의 구성요소로 하나의 연결점을 가리킨다. (노드 = 정점)

간선 (Edge)

→ 두 정점을 연결하는 선을 말한다

차수 (Degree)

→ 정점에 연결된 간선의 수를 말한다

그래프의 유형

무향 그래프 (Undirected Graph)
- 간선에 방향이 없는 그래프를 말한다.
- 두 정점 사이에 간선이 존재하면 그 간선은 양방향으로 표시된다.
유향 그래프 (Directed Graph)
- 간선에 방향이 있는 그래프를 말한다.
- 간선에 방향이 있기 때문에 한 정점에서 다른 정점으로 가는 간선과 반대 방향으로 가는 간선이 모두 존재할 수 있다.
가중치 그래프 (Weighted Graph)
- 간선에 가중치(가치, 비용)가 있는 그래프를 말한다.
- 간선에 가중치가 있기 때문에 경로의 길이를 측정하는 데 사용할 수 있다.
사이클 없는 방향 그래프 (DAG, Directed Acyclic Graph)
- 유향 그래프 중에서 방향 사이클이 없는 그래프를 말한다.
- 한 정점에서 출발하여 자기 자신으로 돌아오는 경로가 없는 그래프이다.
완전그래프 (Complete Graph)
- 모든 정점이 간선으로 연결되어 있는 그래프를 말한다.
- 즉, 정점의 개수가 N일 때, N(N-1)/2 개의 간선을 가지는 그래프이다.
- 완전그래프는 최대한 밀도있게 정점과 간선이 연결된 형태이며, 각 정점은 서로 인접해있다.
부분 그래프 (Subgraph)
- 그래프 G에서 일부의 정점과 간선을 제외하여 얻어진 그래프 H를 말한다.
- H는 G의 부분집합이며, H에서의 정점과 간선은 G에서의 정점과 간선의 일부이다.
- 즉, G의 일부분을 떼어내서 만든 그래프이다.

그래프의 표현 방법

그래프는 크게 세 가지 방법으로 표현할 수 있다.

1. 인접 행렬(Adjacency Matrix)

인접 행렬은 2차원 배열을 사용하여 그래프를 표현하는 방법이다.

    A B C D
A |0 1 1 0|
B |1 0 1 1|
C |1 1 0 1|
D |0 1 1 0|

위의 행렬에서 A와 B가 연결되어 있으므로 행렬의 (1,2)와 (2,1)이 1로 표시된다.

인접 행렬은 구현이 간단하고 특정 노드와 연결된 모든 노드를 찾는 데에는 O(1)의 시간 복잡도를 가지지만, 노드의 개수가 많아질수록 불필요한 메모리를 많이 차지하게 되는 단점이 있습니다.

메모리가 $N^2$만큼 차지하기 때문에 노드수가 많아진다면 다른 방식으로 표현하는 것이 좋다.

2. 인접 리스트(Adjacency List)

인접 리스트는 연결 리스트를 사용하여 그래프를 표현하는 방법이다.

A -> B -> C
B -> A -> C -> D
C -> A -> B -> D
D -> B -> C

A 노드에 B와 C가 연결되어 있다면 A → B → C 와 같은 연결리스트 형태로 나타낼 수 있다.

인접 리스트는 메모리를 효율적으로 사용하기 때문에 노드의 개수가 많을 경우에 유리하다. 하지만 특정 노드와 연결된 모든 노드를 찾는 데에는 O(노드의 차수)의 시간 복잡도를 가진다.

따라서, 노드의 조회를 많이 하게 된다면 인접행렬 형태의 표현이 더 좋을 수 있다.

3. 간선 리스트(Edge List)

간선 리스트는 간선을 하나씩 리스트로 표현하는 방법이다.

(A, B), (A, C), (B, C), (B, D), (C, D)

각각의 연결 자체를 리스트 형태로 가지고 있는다.

간선 리스트는 구현이 간단하고 간선의 개수가 많지 않은 경우에는 메모리를 효율적으로 사용할 수 있다. 하지만 특정 노드와 연결된 모든 노드를 찾는 데에는 O(간선의 개수)의 시간 복잡도를 가진다.

결론

문제에서 주어지는 노드의 개수, 간선의 개수, 조회를 많이 할 지, 삽입, 삭제를 많이 할 지 등등 여러가지를 고려해서 인접행렬, 인접 리스트, 간선 리스트 중 적절한 표현 방식을 선택해야 한다.