[자료구조] 그래프 (Graph)

그래프 (Graph)

• 정점과 간선으로 이루어진 자료구조 (Cyclic)
• 지하철 노선도, 통신 네트워크 등에 사용

그래프의 종류

(1) 무방향 그래프 : 간선에 방향이 없는 그래프 (양방향 이동 가능)

(2) 방향 그래프 : 간선에 방향이 있는 그래프 (해당 방향으로만 이동 가능)

(3) 가중치 그래프 : 간선에 값이 있는 그래프 (이동 비용)

(4) 완전 그래프 : 모든 정점이 서로 연결되어 있는 그래프, 노드가 N 개일 경우, 간선의 수는 N(N-1)/2개

그래프 탐색

(1) 깊이 우선 탐색 (Depth First Search; DFS)

DFS는 그래프 또는 트리에서 모든 노드를 탐색하는 알고리즘으로 스택 또는 재귀 함수를 사용하여 구현할 수 있다.

1. 시작 노드를 방문하고 방문한 노드를 스택에 push
2. 스택에서 노드를 pop하여 현재 노드로 설정
3. 현재 노드와 연결된 인접한 미방문 노드가 있다면, 그 중 하나를 방문하고 방문한 노드를 스택에 push
4. 이전 단계를 반복하여 스택이 비어있을 때까지 진행하고, 만약 현재 노드와 연결된 미방문 노드가 없다면, 스택에서 이전 노드로 돌아간다.
5. 스택이 비어있고 더 이상 방문할 노드가 없으면 탐색을 종료

주로 재귀 함수를 사용하여 구현하지만 재귀 호출이 너무 많이 발생하면 스택 오버플로우가 발생할 수 있다. 이를 방지하기 위해 반복문과 스택을 사용하여 비재귀적으로 구현할 수도 있다.

(2) 너비 우선 탐색 (Breath First Search; BFS)

BFS는 그래프 또는 트리에서 가까운 노드부터 탐색하는 알고리즘으로, 큐를 사용하여 구현할 수 있다.

1. 시작 노드를 방문하고 방문한 노드를 큐에 enqueue(삽입)
2. 큐에서 노드를 dequeue(삭제)하여 현재 노드로 설정
3. 현재 노드와 연결된 모든 인접한 미방문 노드를 방문하고 방문한 노드를 큐에 enqueue
4. 이전 단계를 반복하여 큐가 비어있을 때까지 진행하고, 큐가 비어있을 때는 탐색을 종료한다.

레벨 순서대로 탐색을 진행한다. 즉, 현재 노드와 거리가 1인 인접한 노드들을 모두 방문한 후에 거리가 2인 노드들을 방문한다. 이러한 특성으로 인해 BFS는 최단 경로 문제에서 많이 활용된다.

그래프의 구현

(1) 인접 행렬 (Adjacency Matrix)

• 2차원 배열로 구현
• 그래프의 노드 수를 n이라고 할 때, n x n 크기의 배열을 사용
• 인접 행렬 G[i][j]의 값은 노드 i와 j 사이의 간선의 존재 여부를 나타낸다.
• 간선이 존재하면 1또는 가중치 값을 가지며, 간선이 없으면 0으로 표시
• 무방향 그래프에서 인접 행렬은 대칭 행렬이 된다.
• 노드 간의 연결 여부를 상수 시간(O(1))에 확인할 수 있다.
• 그러나 그래프 간선의 수가 적은 경우에는 불필요한 메모리를 사용하게 된다.

(2) 인접 리스트 (Adjacency List)

• 연결 리스트로 구현
• 그래프의 각 노드에 대해 연결 리스트를 사용하여 해당 노드와 인접한 노드들을 저장
• 각 노드마다 인접한 노드의 리스트를 저장하므로, 노드의 개수에 비례하는 메모리를 사용한다.
• 그래프 간선의 수가 적은 경우에 유리하며, 메모리를 효율적으로 사용한다.
• 각 노드의 인접한 노드들을 순차적으로 탐색하는데 유리하다.
• 노드 간의 연결 여부를 확인하기 위해 O(degree)의 시간이 소요된다. (degree: 노드의 차수)

(3) 인접 행렬 vs 인접 리스트

• 인접 행렬: 노드의 개수가 적고 edge의 수가 많을 때 유리 - 밀집 그래프(Dense Graph)
• 인접 리스트: 노드의 개수가 많고 edge의 수가 적을 때 유리 - 희소 그래프(Sparse Graph)