그래프 #Graph [ 수정 내역 ] [ 수정 ]

최근 수정: 6년 전

1. 개요

Graph.

수학에서의 그래프와는 다르다.

정점과 간선으로 표현되는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료구조. 여러 정점들이 연결된 형태를 나타낸다.

2. 용어

• 정점(vertex) 또는 노드(node) : 점.
• 간선(edge) : 노드를 연결하는 선.
• 가중치(weight) : 간선의 비용.
• 방향성 : 간선의 방향의 유무. 방향성이 있다면 일방통행, 없다면 양방향 통행이라고 생각하면 된다.
• 경로(path) : 한 정점에서 다른 정점까지의 경로. 최단 경로는 최소 비용으로 연결된 것을 말한다.
• 사이클(cycle) : 한 정점에서 다시 같은 정점으로 돌아오는 경로.
• 차수(degree) : 한 정점에서 연결된 간선의 개수. 만약, 방향성이 있는 그래프라면 들어오는 간선 (indegree), 나가는 간선 (outdegree)라고 한다.

3. 그래프의 표현

그래프를 표현하는 방법으로 크게 3가지가 있다.

3.1. 인접 행렬

정점의 크기가 V라고 할 때, V * V의 2차원 배열을 이용한다.

graph[i][j] : i에서 j로 연결되어 있는 상태. 1이면 연결, 0이면 연결 안된 것을 나타낸다. 1 대신에 가중치를 넣을 수도 있다.

상당히 간편한 방법이지만, V가 크면 사용 불능에 가깝다. [1] 따라서 거의 사용되지 않는다.

3.2. 인접 리스트

각 정점에서 연결된 정점들을 리스트 형태로 구현.

graph[i] : i 번 정점에서 연결된 정점들.

위의 인접 행렬에 비해 조금 복잡한 방법. 일단 리스트의 배열 형태로 구현해야 하므로 상당히 복잡하다. 다행히 C++에는 벡터가 있지만 C언어는 직접 링크드 리스트를 구현해야 한다. [2]

구현은 조금 복잡하지만 상당히 많이 사용된다. 모든 그래프는 인접 리스트로 구현해도 될 정도. 반드시 알아두자!

3.3. 간선 리스트

말 그대로 간선들의 정보를 저장한다.

graph[i] : i 번째 간선. (연결된 정점 2개를 가지고 있다.)

많이 사용되지 않는다.

4. 그래프의 탐색

4.1. DFS

깊이 우선 탐색. 자세한 건 해당 문서 참고.

4.2. BFS

너비 우선 탐색. 자세한 건 해당 문서 참고.

5. 같이 보기

DAG : 방향성 있는 사이클 없는 그래프.

트리 : 사이클 없는 그래프. (간선의 수 == 정점의 수 - 1)

최단 경로 : 최소 비용으로 연결된 경로.

알고리즘 프로젝트

[1] V가 10만 정도만 되어도 10만 * 10만 = 100억...이라는 엄청난 메모리가 필요하다. 탐색 시의 엄청난 시간은 덤.

[2] 또는 벡터 처럼 동적 배열을 구현해도 된다.