그래프 자료구조의 기본 개념과 주요 알고리즘
그래프는 노드(정점)와 이 노드를 연결하는 간선(에지 또는 아크)으로 구성된 자료구조입니다. 컴퓨터 과학에서 다양한 시스템, 네트워크, 관계 등을 모델링하는 데 활용됩니다. 이 글에서는 그래프의 기본적인 개념부터 주요 표현 방식, 그리고 BFS, DFS, 최단 경로, 위상 정렬 등 핵심 알고리즘들을 C 언어 기반으로 살펴보겠습니다.
그래프 기본 용어
- 정점 (Vertex, Node): 그래프의 기본 구성 요소. 일반적으로 V 또는 |V|로 전체 정점의 개수를 나타냅니다.
- 간선 (Edge, Arc): 두 정점을 연결하는 선. E 또는 |E|로 전체 간선의 개수를 나타냅니다.
- 무방향 간선 (Undirected Edge): 두 정점 v와 w를 연결하는 (v, w) 형태의 간선으로, 방향이 없습니다.
- 방향 간선 (Directed Edge, Arc): 정점 v에서 정점 w로 향하는 <v, w> 형태의 간선입니다.
- 무방향 그래프 (Undirected Graph, UDG): 모든 간선이 무방향인 그래프입니다.
- 방향 그래프 (Directed Graph, DG): 모든 간선이 방향을 가지는 그래프입니다.
- 무방향 가중 그래프 (Undirected Weighted Graph, UDN): 무방향 간선에 가중치(비용)가 부여된 그래프입니다.
- 방향 가중 그래프 (Directed Weighted Graph, DN): 방향 간선에 가중치(비용)가 부여된 그래프입니다.
- 연결 그래프 (Connected Graph): 무방향 그래프에서 임의의 두 정점 사이에 항상 경로가 존재하는 그래프입니다.
- 연결 요소 (Connected Component): 비연결 그래프 내에서 서로 연결된 정점들의 부분 그래프입니다.
그래프 저장 방식
그래프를 컴퓨터 메모리에 저장하는 방식은 주로 인접 행렬과 인접 리스트 두 가지가 있습니다. 각 방식은 장단점이 뚜렷하여 그래프의 종류와 수행할 연산에 따라 적절한 방식을 선택해야 합니다.
인접 행렬 (Adjacency Matrix)
인접 행렬은 2차원 배열을 사용하여 그래프를 표현하는 방식입니다. 정점의 개수를 N이라고 할 때 N x N 크기의 행렬을 사용합니다. adjMatrix[i][j]의 값은 정점 i와 정점 j 사이에 간선이 존재하는지, 또는 가중치가 얼마인지를 나타냅니다.
- 간선 존재 여부: 무방향/방향 그래프에서는 1(존재) 또는 0(미존재)으로 표현합니다.
- 가중치: 가중 그래프에서는 간선의 가중치를 직접 저장하고, 간선이 없는 경우 매우 큰 값(무한대)이나 0으로 표현합니다.
인접 행렬의 구조는 다음과 같이 정의할 수 있습니다.
#define MAX_NODES 100
#define NODE_TYPE char
#define INF 9999 // 무한대 값을 표현 (Integer Max value도 가능)
// 그래프의 종류를 정의하는 열거형
typedef enum { DIRECTED, DIRECTED_WEIGHTED, UNDIRECTED, UNDIRECTED_WEIGHTED } GraphKind;
// 인접 행렬 방식의 그래프 구조체
typedef struct {
NODE_TYPE vertices[MAX_NODES]; // 정점 데이터를 저장하는 배열
int adjMatrix[MAX_NODES][MAX_NODES]; // 간선 정보 (가중치)를 저장하는 2차원 배열
int numVertices; // 정점의 수
int numEdges; // 간선의 수
GraphKind kind; // 그래프의 종류
} AdjacencyMatrixGraph;
예를 들어, 4개의 정점(A, B, C, D)을 가진 무방향 그래프에서 A-B, A-C, B-D 간선이 있다면, 인접 행렬은 다음과 같을 수 있습니다 (1은 간선 존재, 0은 미존재):
A B C D
A 0 1 1 0
B 1 0 0 1
C 1 0 0 0
D 0 1 0 0
무방향 그래프의 인접 행렬은 주대각선을 기준으로 대칭적인 특징을 가집니다. 방향 그래프의 경우 대칭이 아닐 수 있습니다.
인접 리스트 (Adjacency List)
인접 리스트는 각 정점에 연결된 정점들을 연결 리스트로 저장하는 방식입니다. 정점의 수 N에 대해 N개의 연결 리스트를 관리합니다. 각 연결 리스트의 요소는 해당 정점과 인접한 정점의 인덱스 및 간선 가중치를 포함할 수 있습니다.
#define MAX_NODES 100
#define NODE_TYPE char
#define INF 9999
typedef enum { DIRECTED, DIRECTED_WEIGHTED, UNDIRECTED, UNDIRECTED_WEIGHTED } GraphKind;
// 간선 노드 (연결 리스트의 요소)
typedef struct EdgeNode {
int targetNodeIdx; // 간선이 연결되는 대상 정점의 인덱스
struct EdgeNode *nextEdge; // 다음 간선 노드를 가리키는 포인터
int weight; // 간선의 가중치
} EdgeNode;
// 정점 노드 (정점 배열의 요소)
typedef struct NodeEntry {
NODE_TYPE data; // 정점 데이터
EdgeNode *firstEdge; // 해당 정점과 연결된 첫 번째 간선 노드를 가리키는 포인터
} NodeEntry, AdjList[MAX_NODES]; // AdjList는 NodeEntry 타입의 배열
// 인접 리스트 방식의 그래프 구조체
typedef struct {
AdjList nodes; // 정점 엔트리 배열 (각 정점은 연결 리스트의 헤드)
int numVertices; // 정점의 수
int numEdges; // 간선의 수
GraphKind kind; // 그래프의 종류
} AdjacencyListGraph;
인접 리스트는 특히 간선의 수가 적은 희소(sparse) 그래프에 효율적입니다.
기타 저장 방식
십자 리스트(Orthogonal List)나 인접 다중 리스트(Adjacency Multilist)와 같은 방식도 있지만, 여기서는 다루지 않습니다.
인접 행렬 기반 그래프 연산
인접 행렬 구조를 활용하여 그래프의 기본 연산, 탐색, 최단 경로, 위상 정렬 등을 구현하는 방법을 살펴봅니다.
기본 연산
#include <stdio.h> // for printf
#include <stdlib.h> // for malloc
// (이전 정의된 GraphKind, MAX_NODES, NODE_TYPE, INF, AdjacencyMatrixGraph 구조체 사용)
// 정점 데이터로 인덱스를 찾는 함수
int findNodeIndex(AdjacencyMatrixGraph graph, NODE_TYPE nodeVal) {
for (int i = 0; i < graph.numVertices; i++) {
if (graph.vertices[i] == nodeVal) {
return i;
}
}
return -1; // 찾지 못함
}
// 특정 정점과 인접한 첫 번째 정점의 인덱스를 찾는 함수
int getFirstNeighbor(AdjacencyMatrixGraph graph, int nodeIdx) {
for (int j = 0; j < graph.numVertices; j++) {
if (graph.adjMatrix[nodeIdx][j] != 0 && graph.adjMatrix[nodeIdx][j] != INF) {
return j;
}
}
return -1; // 인접한 정점이 없음
}
// 특정 정점의 다음 인접 정점을 찾는 함수 (prevNeighborIdx 이후)
int getNextNeighbor(AdjacencyMatrixGraph graph, int nodeIdx, int prevNeighborIdx) {
for (int j = prevNeighborIdx + 1; j < graph.numVertices; j++) {
if (graph.adjMatrix[nodeIdx][j] != 0 && graph.adjMatrix[nodeIdx][j] != INF) {
return j;
}
}
return -1; // 다음 인접 정점이 없음
}
// 그래프에 정점을 삽입하는 함수
void insertVertex(AdjacencyMatrixGraph *graph, NODE_TYPE nodeVal) {
if (graph->numVertices < MAX_NODES) {
graph->vertices[graph->numVertices++] = nodeVal;
// 새 정점에 대한 간선은 기본적으로 0 또는 INF (가중치 그래프)으로 초기화되어 있다고 가정
// 실제 구현에서는 새 행/열을 0 또는 INF로 초기화하는 로직이 필요
}
}
// 두 정점 사이에 간선을 삽입하는 함수
void insertEdge(AdjacencyMatrixGraph *graph, NODE_TYPE startNodeVal, NODE_TYPE endNodeVal, int weight) {
int u = findNodeIndex(*graph, startNodeVal);
int v = findNodeIndex(*graph, endNodeVal);
if (u == -1 || v == -1) return; // 정점을 찾지 못하면 종료
if (graph->kind == UNDIRECTED || graph->kind == UNDIRECTED_WEIGHTED) {
graph->adjMatrix[u][v] = weight;
graph->adjMatrix[v][u] = weight;
} else if (graph->kind == DIRECTED || graph->kind == DIRECTED_WEIGHTED) {
graph->adjMatrix[u][v] = weight;
}
graph->numEdges++;
}
이 외에도 특정 정점으로 들어오는 간선(선행 정점)을 찾는 getFirstPredecessor나 getNextPredecessor와 같은 함수도 유사한 방식으로 구현할 수 있습니다.
그래프 탐색 (Graph Traversal)
그래프 탐색은 그래프의 모든 정점이나 특정 목적 정점을 체계적으로 방문하는 과정입니다. 주로 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS)이 사용됩니다.
너비 우선 탐색 (Breadth-First Search, BFS)
BFS는 시작 정점에서부터 가까운 정점들을 먼저 탐색하고 점차 멀리 있는 정점들을 탐색하는 방식입니다. 큐(Queue) 자료구조를 사용하여 구현합니다. 각 정점의 방문 여부를 추적하기 위해 visited 배열을 사용합니다.
// 큐 관련 기본 구조체 및 함수 (인접 행렬 및 리스트 공통)
typedef struct {
int items[MAX_NODES];
int front, rear;
} Queue;
void initQueue(Queue *q) {
q->front = -1;
q->rear = -1;
}
int isEmpty(Queue *q) {
return q->front == -1;
}
void enqueue(Queue *q, int value) {
if (q->rear == MAX_NODES - 1) { // 큐가 가득 참
fprintf(stderr, "Queue is full!\n");
return;
}
if (q->front == -1) { // 첫 번째 요소
q->front = 0;
}
q->rear++;
q->items[q->rear] = value;
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
fprintf(stderr, "Queue is empty!\n");
return -1; // 에러 또는 빈 큐
}
int item = q->items[q->front];
q->front++;
if (q->front > q->rear) { // 큐가 비었을 때 초기화
q->front = q->rear = -1;
}
return item;
}
// 방문 여부를 저장하는 전역 배열 (또는 함수 인자로 전달)
static int visited[MAX_NODES];
// 실제 BFS 로직
void bfsTraversal(AdjacencyMatrixGraph graph, int startNodeIdx) {
Queue q;
initQueue(&q);
// 시작 노드 방문 및 큐에 추가
visited[startNodeIdx] = 1;
printf("%c ", graph.vertices[startNodeIdx]);
enqueue(&q, startNodeIdx);
while (!isEmpty(&q)) {
int currentNode = dequeue(&q);
// 현재 노드의 모든 인접 노드를 탐색
for (int neighbor = getFirstNeighbor(graph, currentNode);
neighbor != -1;
neighbor = getNextNeighbor(graph, currentNode, neighbor)) {
if (!visited[neighbor]) {
visited[neighbor] = 1;
printf("%c ", graph.vertices[neighbor]);
enqueue(&q, neighbor);
}
}
}
}
// 전체 그래프를 BFS로 탐색 (비연결 그래프 포함)
void fullBfs(AdjacencyMatrixGraph graph, int startIdx) {
for (int i = 0; i < graph.numVertices; i++) {
visited[i] = 0; // 모든 노드를 미방문 상태로 초기화
}
// 시작 인덱스부터 BFS 수행
bfsTraversal(graph, startIdx);
// 나머지 연결 요소들을 탐색
for (int i = 0; i < graph.numVertices; i++) {
if (!visited[i]) {
bfsTraversal(graph, i);
}
}
printf("\n");
}
BFS는 최단 경로(가중치가 없는 경우)를 찾는 데 효과적이며, 그래프의 너비를 우선적으로 탐색하기 때문에 레벨 순서 탐색이라고도 불립니다. 비연결 그래프의 경우, 모든 정점을 방문하기 위해 fullBfs와 같이 모든 정점을 순회하며 아직 방문하지 않은 정점에 대해 BFS를 시작해야 합니다.
깊이 우선 탐색 (Depth-First Search, DFS)
DFS는 한 방향으로 갈 수 있는 한 최대한 깊이 탐색하다가 더 이상 갈 곳이 없으면 되돌아와(백트래킹) 다른 방향으로 탐색을 계속하는 방식입니다. 주로 재귀 함수 또는 스택을 사용하여 구현합니다.
// 실제 DFS 로직 (재귀)
void dfsTraversal(AdjacencyMatrixGraph graph, int currentNodeIdx) {
visited[currentNodeIdx] = 1;
printf("%c ", graph.vertices[currentNodeIdx]);
// 현재 노드의 모든 인접 노드를 재귀적으로 탐색
for (int neighbor = getFirstNeighbor(graph, currentNodeIdx);
neighbor != -1;
neighbor = getNextNeighbor(graph, currentNodeIdx, neighbor)) {
if (!visited[neighbor]) {
dfsTraversal(graph, neighbor);
}
}
}
// 전체 그래프를 DFS로 탐색 (비연결 그래프 포함)
void fullDfs(AdjacencyMatrixGraph graph, int startIdx) {
for (int i = 0; i < graph.numVertices; i++) {
visited[i] = 0; // 모든 노드를 미방문 상태로 초기화
}
// 시작 인덱스부터 DFS 수행
dfsTraversal(graph, startIdx);
// 나머지 연결 요소들을 탐색
for (int i = 0; i < graph.numVertices; i++) {
if (!visited[i]) {
dfsTraversal(graph, i);
}
}
printf("\n");
}
DFS는 경로 찾기, 사이클 감지, 위상 정렬 등 다양한 문제 해결에 사용됩니다.
최단 경로 알고리즘 (Shortest Path Algorithms)
두 정점 사이의 최단 경로를 찾는 알고리즘은 가중치 그래프에서 매우 중요합니다. 여기서는 세 가지 주요 알고리즘을 다룹니다.
BFS 기반 최단 경로 (가중치 없는 그래프)
가중치가 없는 그래프에서 최단 경로는 BFS를 통해 쉽게 찾을 수 있습니다. 시작 정점에서 각 정점까지의 거리를 distances 배열에 저장하고, 경로를 추적하기 위해 predecessors 배열을 사용합니다.
static int distances[MAX_NODES];
static int predecessors[MAX_NODES];
void bfsShortestPath(AdjacencyMatrixGraph graph, int startNodeIdx) {
Queue q;
initQueue(&q);
for (int i = 0; i < graph.numVertices; i++) {
distances[i] = INF; // 모든 거리를 무한대로 초기화
predecessors[i] = -1; // 선행 노드 없음으로 초기화
visited[i] = 0; // 방문 여부 초기화
}
distances[startNodeIdx] = 0;
visited[startNodeIdx] = 1;
enqueue(&q, startNodeIdx);
while (!isEmpty(&q)) {
int current = dequeue(&q);
for (int neighbor = getFirstNeighbor(graph, current);
neighbor != -1;
neighbor = getNextNeighbor(graph, current, neighbor)) {
if (!visited[neighbor]) {
visited[neighbor] = 1;
distances[neighbor] = distances[current] + 1; // 간선 가중치가 1이라고 가정
predecessors[neighbor] = current;
enqueue(&q, neighbor);
}
}
}
}
다익스트라 알고리즘 (Dijkstra's Algorithm)
다익스트라 알고리즘은 하나의 시작 정점에서 다른 모든 정점까지의 최단 경로를 찾는 단일-소스 최단 경로 알고리즘입니다. 음의 가중치를 허용하지 않습니다. 그리디(Greedy) 방식을 사용하며, finalized 배열로 최단 경로가 확정된 정점을 표시합니다.
static int shortestDistances[MAX_NODES];
static int pathPredecessors[MAX_NODES];
static int finalized[MAX_NODES]; // 최단 경로가 확정된 노드
void dijkstra(AdjacencyMatrixGraph graph, int startNodeIdx) {
for (int i = 0; i < graph.numVertices; i++) {
finalized[i] = 0; // 모든 노드의 최단 경로 미확정
shortestDistances[i] = graph.adjMatrix[startNodeIdx][i]; // 시작 노드로부터 직접 연결된 거리
if (graph.adjMatrix[startNodeIdx][i] != 0 && graph.adjMatrix[startNodeIdx][i] != INF) {
pathPredecessors[i] = startNodeIdx; // 시작 노드에서 직접 연결된 경우
} else {
pathPredecessors[i] = -1; // 경로 없음
}
}
finalized[startNodeIdx] = 1; // 시작 노드의 최단 거리는 0으로 확정
shortestDistances[startNodeIdx] = 0;
// 나머지 N-1개의 노드에 대해 최단 경로를 찾음
for (int i = 0; i < graph.numVertices - 1; i++) {
int minDistance = INF;
int nextNodeToFinalize = -1;
// 아직 확정되지 않은 노드 중 가장 짧은 거리의 노드를 선택
for (int v = 0; v < graph.numVertices; v++) {
if (!finalized[v] && shortestDistances[v] < minDistance) {
minDistance = shortestDistances[v];
nextNodeToFinalize = v;
}
}
if (nextNodeToFinalize == -1) break; // 더 이상 연결된 노드가 없음
finalized[nextNodeToFinalize] = 1; // 해당 노드의 최단 경로 확정
// 선택된 노드를 거쳐 다른 노드로 가는 경로가 더 짧은지 확인 및 업데이트
for (int v = 0; v < graph.numVertices; v++) {
if (!finalized[v] && graph.adjMatrix[nextNodeToFinalize][v] != 0 && graph.adjMatrix[nextNodeToFinalize][v] != INF) {
if (shortestDistances[nextNodeToFinalize] + graph.adjMatrix[nextNodeToFinalize][v] < shortestDistances[v]) {
shortestDistances[v] = shortestDistances[nextNodeToFinalize] + graph.adjMatrix[nextNodeToFinalize][v];
pathPredecessors[v] = nextNodeToFinalize;
}
}
}
}
}
플로이드-워셜 알고리즘 (Floyd-Warshall Algorithm)
플로이드-워셜 알고리즘은 모든 정점 쌍 간의 최단 경로를 찾는 동적 프로그래밍 기반 알고리즘입니다. 음의 가중치를 허용하지만, 음의 사이클이 있는 경우에는 제대로 작동하지 않습니다. 3중 반복문을 사용하여 구현하며, 중간 정점을 점진적으로 고려하여 최단 경로를 갱신합니다.
static int allPairsDistances[MAX_NODES][MAX_NODES];
static int allPairsPaths[MAX_NODES][MAX_NODES];
void floydWarshall(AdjacencyMatrixGraph graph) {
// 초기화: 직접 연결된 간선으로 거리 및 경로 설정
for (int i = 0; i < graph.numVertices; i++) {
for (int j = 0; j < graph.numVertices; j++) {
if (i == j) {
allPairsDistances[i][j] = 0;
} else if (graph.adjMatrix[i][j] != 0 && graph.adjMatrix[i][j] != INF) {
allPairsDistances[i][j] = graph.adjMatrix[i][j];
allPairsPaths[i][j] = i; // i에서 j로 직접 가는 경우, 선행 노드는 i
} else {
allPairsDistances[i][j] = INF;
allPairsPaths[i][j] = -1; // 경로 없음
}
}
}
// k를 중간 정점으로 사용하여 최단 경로 갱신
for (int k = 0; k < graph.numVertices; k++) { // 중간 노드
for (int i = 0; i < graph.numVertices; i++) { // 시작 노드
for (int j = 0; j < graph.numVertices; j++) { // 도착 노드
// i -> k -> j 경로가 현재 i -> j 경로보다 짧은 경우
if (allPairsDistances[i][k] != INF && allPairsDistances[k][j] != INF) {
if (allPairsDistances[i][k] + allPairsDistances[k][j] < allPairsDistances[i][j]) {
allPairsDistances[i][j] = allPairsDistances[i][k] + allPairsDistances[k][j];
allPairsPaths[i][j] = allPairsPaths[k][j]; // 경로 업데이트 (k를 거쳐 j로)
}
}
}
}
}
}
위상 정렬 (Topological Sort)
위상 정렬은 방향 비순환 그래프(DAG, Directed Acyclic Graph)의 정점들을 방향성을 유지하면서 일렬로 나열하는 방법입니다. 즉, 모든 방향 간선 <u, v>에 대해 u가 v보다 먼저 오도록 정점들을 나열합니다. AOV(Activity On Vertex) 네트워크의 선행 관계를 분석하는 데 사용됩니다.
진입 차수(In-degree) 기반 위상 정렬
진입 차수 기반 방식은 진입 차수가 0인 정점들을 큐에 넣고, 큐에서 정점을 하나씩 꺼내면서 해당 정점에서 나가는 간선들을 제거하고 인접 정점들의 진입 차수를 감소시킵니다. 감소된 진입 차수가 0이 되는 정점은 다시 큐에 넣습니다. 모든 정점을 처리할 때까지 이 과정을 반복합니다.
static int sortedOrder[MAX_NODES]; // 위상 정렬 결과 저장
// 각 정점의 진입 차수를 계산하는 함수
void calculateInDegrees(AdjacencyMatrixGraph graph, int inDegrees[]) {
for (int i = 0; i < graph.numVertices; i++) {
inDegrees[i] = 0; // 초기화
}
for (int i = 0; i < graph.numVertices; i++) {
for (int j = 0; j < graph.numVertices; j++) {
if (graph.adjMatrix[i][j] != 0 && graph.adjMatrix[i][j] != INF) {
inDegrees[j]++; // i -> j 간선이 존재하면 j의 진입 차수 증가
}
}
}
}
// 위상 정렬 수행
int topologicalSort(AdjacencyMatrixGraph graph) {
int inDegrees[MAX_NODES];
calculateInDegrees(graph, inDegrees);
Queue q;
initQueue(&q);
// 진입 차수가 0인 모든 정점을 큐에 추가
for (int i = 0; i < graph.numVertices; i++) {
if (inDegrees[i] == 0) {
enqueue(&q, i);
}
}
int count = 0; // 정렬된 정점의 수
while (!isEmpty(&q)) {
int current = dequeue(&q);
sortedOrder[count++] = current; // 정렬 결과에 추가
// 현재 정점에서 나가는 모든 간선을 처리
for (int neighbor = getFirstNeighbor(graph, current);
neighbor != -1;
neighbor = getNextNeighbor(graph, current, neighbor)) {
inDegrees[neighbor]--; // 인접 정점의 진입 차수 감소
if (inDegrees[neighbor] == 0) {
enqueue(&q, neighbor); // 진입 차수가 0이 되면 큐에 추가
}
}
}
// 그래프에 사이클이 있으면 모든 정점을 정렬할 수 없음
return count == graph.numVertices;
}
DFS 기반 위상 정렬
DFS 기반 위상 정렬은 DFS 탐색이 완료되는 순서를 역순으로 기록하면 위상 정렬이 됩니다. 즉, DFS 탐색에서 한 정점의 모든 후속 정점 탐색이 완료되어 스택에서 팝되는 시점을 기준으로 정렬합니다. 가장 늦게 완료되는 정점이 위상 정렬의 가장 앞에 위치하게 됩니다.
static int dfsVisited[MAX_NODES];
static int dfsStack[MAX_NODES];
static int stackTop; // 스택의 top 포인터 (next free position)
void dfsTopoUtil(AdjacencyMatrixGraph graph, int currentNodeIdx) {
dfsVisited[currentNodeIdx] = 1;
for (int neighbor = getFirstNeighbor(graph, currentNodeIdx);
neighbor != -1;
neighbor = getNextNeighbor(graph, currentNodeIdx, neighbor)) {
if (!dfsVisited[neighbor]) {
dfsTopoUtil(graph, neighbor);
}
}
// 모든 인접 노드 방문이 끝난 후 스택에 추가
dfsStack[stackTop++] = currentNodeIdx;
}
int dfsTopologicalSort(AdjacencyMatrixGraph graph) {
for (int i = 0; i < graph.numVertices; i++) {
dfsVisited[i] = 0;
}
stackTop = 0; // 스택 초기화
for (int i = 0; i < graph.numVertices; i++) {
if (!dfsVisited[i]) {
dfsTopoUtil(graph, i);
}
}
// 스택에 저장된 순서의 역순이 위상 정렬 결과
for (int i = 0; i < graph.numVertices; i++) {
sortedOrder[i] = dfsStack[graph.numVertices - 1 - i];
}
// 이 구현은 사이클 감지 기능이 명시적이지 않으므로,
// 사이클이 있는 경우에도 결과가 나오지만 유효하지 않을 수 있습니다.
// 실제 사이클 감지는 DFS 중 백엣지(back-edge)를 통해 구현됩니다.
return 1; // 성공 (사이클 여부 판단은 별도 로직 필요)
}
인접 리스트 기반 그래프 연산
인접 리스트는 희소 그래프에 더 효율적이며, 정점의 인접 정점을 찾는 데 필요한 시간이 해당 정점의 차수에 비례합니다. 기본 연산들을 인접 리스트에 맞춰 재정의해야 합니다.
기본 연산
// (이전 정의된 GraphKind, MAX_NODES, NODE_TYPE, INF, EdgeNode, NodeEntry, AdjList, AdjacencyListGraph 구조체 사용)
// 정점 데이터로 인덱스를 찾는 함수 (인접 행렬과 동일)
int findNodeIndexAL(AdjacencyListGraph graph, NODE_TYPE nodeVal) {
for (int i = 0; i < graph.numVertices; i++) {
if (graph.nodes[i].data == nodeVal) {
return i;
}
}
return -1;
}
// 특정 정점 (u)에서 다른 정점 (v)로의 간선 가중치를 찾는 함수
int getEdgeWeightAL(AdjacencyListGraph graph, int u, int v) {
EdgeNode *current = graph.nodes[u].firstEdge;
while (current != NULL) {
if (current->targetNodeIdx == v) {
return current->weight;
}
current = current->nextEdge;
}
return INF; // 간선이 없거나 무한대
}
// 특정 정점과 인접한 첫 번째 정점의 인덱스를 찾는 함수
int getFirstNeighborAL(AdjacencyListGraph graph, int nodeIdx) {
if (graph.nodes[nodeIdx].firstEdge != NULL) {
return graph.nodes[nodeIdx].firstEdge->targetNodeIdx;
}
return -1;
}
// 특정 정점의 다음 인접 정점을 찾는 함수 (prevNeighborIdx 이후)
int getNextNeighborAL(AdjacencyListGraph graph, int nodeIdx, int prevNeighborIdx) {
EdgeNode *current = graph.nodes[nodeIdx].firstEdge;
// prevNeighborIdx를 찾아 그 다음 노드를 반환
while (current != NULL && current->targetNodeIdx != prevNeighborIdx) {
current = current->nextEdge;
}
if (current != NULL && current->nextEdge != NULL) {
return current->nextEdge->targetNodeIdx;
}
return -1;
}
// 그래프에 정점을 삽입하는 함수
void insertVertexAL(AdjacencyListGraph *graph, NODE_TYPE nodeVal) {
if (graph->numVertices < MAX_NODES) {
graph->nodes[graph->numVertices].data = nodeVal;
graph->nodes[graph->numVertices].firstEdge = NULL; // 초기에는 간선 없음
graph->numVertices++;
}
}
// 두 정점 사이에 간선을 삽입하는 함수
void insertEdgeAL(AdjacencyListGraph *graph, NODE_TYPE startNodeVal, NODE_TYPE endNodeVal, int weight) {
int u = findNodeIndexAL(*graph, startNodeVal);
int v = findNodeIndexAL(*graph, endNodeVal);
if (u == -1 || v == -1) return;
// 새 간선 노드 생성
EdgeNode *newNode = (EdgeNode *)malloc(sizeof(EdgeNode));
if (newNode == NULL) { /* 에러 처리 */ return; }
newNode->targetNodeIdx = v;
newNode->weight = weight;
newNode->nextEdge = graph->nodes[u].firstEdge; // 헤드에 삽입
graph->nodes[u].firstEdge = newNode;
if (graph->kind == UNDIRECTED || graph->kind == UNDIRECTED_WEIGHTED) {
// 무방향 그래프는 양방향 간선 추가
EdgeNode *reverseNode = (EdgeNode *)malloc(sizeof(EdgeNode));
if (reverseNode == NULL) { /* 에러 처리 */ return; }
reverseNode->targetNodeIdx = u;
reverseNode->weight = weight;
reverseNode->nextEdge = graph->nodes[v].firstEdge;
graph->nodes[v].firstEdge = reverseNode;
}
graph->numEdges++;
}
인접 리스트에서의 getFirstPredecessor나 getNextPredecessor 구현은 모든 정점의 리스트를 탐색해야 하므로 O(E) 시간이 소요될 수 있습니다. (E는 간선 수)
탐색, 최단 경로, 위상 정렬 (인접 리스트 버전)
인접 리스트 기반의 탐색, 최단 경로, 위상 정렬 알고리즘은 인접 행렬 버전과 기본적인 로직은 동일합니다. 다만, getFirstNeighbor와 getNextNeighbor 함수 호출 부분이 인접 리스트에 맞게 변경되어야 합니다. 또한, 간선 가중치를 가져오는 graph.adjMatrix[u][v]와 같은 부분은 getEdgeWeightAL(graph, u, v) 등으로 대체되어야 합니다.
// (전역 변수 visited, shortestDistances, pathPredecessors, finalized,
// allPairsDistances, allPairsPaths, sortedOrder, dfsVisited, dfsStack, stackTop 등은 이전 정의와 동일하게 사용)
// BFS (인접 리스트 버전)
void bfsTraversalAL(AdjacencyListGraph graph, int startNodeIdx) {
Queue q;
initQueue(&q);
for (int i = 0; i < graph.numVertices; i++) {
visited[i] = 0;
}
visited[startNodeIdx] = 1;
printf("%c ", graph.nodes[startNodeIdx].data);
enqueue(&q, startNodeIdx);
while (!isEmpty(&q)) {
int current = dequeue(&q);
EdgeNode *edge = graph.nodes[current].firstEdge;
while (edge != NULL) {
int neighbor = edge->targetNodeIdx;
if (!visited[neighbor]) {
visited[neighbor] = 1;
printf("%c ", graph.nodes[neighbor].data);
enqueue(&q, neighbor);
}
edge = edge->nextEdge;
}
}
}
// DFS (인접 리스트 버전)
void dfsTraversalAL(AdjacencyListGraph graph, int currentNodeIdx) {
visited[currentNodeIdx] = 1;
printf("%c ", graph.nodes[currentNodeIdx].data);
EdgeNode *edge = graph.nodes[currentNodeIdx].firstEdge;
while (edge != NULL) {
int neighbor = edge->targetNodeIdx;
if (!visited[neighbor]) {
dfsTraversalAL(graph, neighbor);
}
edge = edge->nextEdge;
}
}
// Dijkstra (인접 리스트 버전) - 간선 가중치 검색만 변경
void dijkstraAL(AdjacencyListGraph graph, int startNodeIdx) {
for (int i = 0; i < graph.numVertices; i++) {
finalized[i] = 0;
shortestDistances[i] = getEdgeWeightAL(graph, startNodeIdx, i); // 간선 가중치 가져오는 함수 사용
if (shortestDistances[i] != INF) {
pathPredecessors[i] = startNodeIdx;
} else {
pathPredecessors[i] = -1;
}
}
finalized[startNodeIdx] = 1;
shortestDistances[startNodeIdx] = 0;
for (int i = 0; i < graph.numVertices - 1; i++) {
int minDistance = INF;
int nextNodeToFinalize = -1;
for (int v = 0; v < graph.numVertices; v++) {
if (!finalized[v] && shortestDistances[v] < minDistance) {
minDistance = shortestDistances[v];
nextNodeToFinalize = v;
}
}
if (nextNodeToFinalize == -1) break;
finalized[nextNodeToFinalize] = 1;
EdgeNode *edge = graph.nodes[nextNodeToFinalize].firstEdge;
while (edge != NULL) {
int neighbor = edge->targetNodeIdx;
if (!finalized[neighbor]) {
if (shortestDistances[nextNodeToFinalize] + edge->weight < shortestDistances[neighbor]) {
shortestDistances[neighbor] = shortestDistances[nextNodeToFinalize] + edge->weight;
pathPredecessors[neighbor] = nextNodeToFinalize;
}
}
edge = edge->nextEdge;
}
}
}
// Floyd-Warshall (인접 리스트 버전) - 초기화 부분에서 간선 가중치 검색만 변경
void floydWarshallAL(AdjacencyListGraph graph) {
for (int i = 0; i < graph.numVertices; i++) {
for (int j = 0; j < graph.numVertices; j++) {
if (i == j) {
allPairsDistances[i][j] = 0;
} else {
allPairsDistances[i][j] = getEdgeWeightAL(graph, i, j); // 간선 가중치 가져오는 함수 사용
if (allPairsDistances[i][j] != INF) {
allPairsPaths[i][j] = i;
} else {
allPairsPaths[i][j] = -1;
}
}
}
}
for (int k = 0; k < graph.numVertices; k++) {
for (int i = 0; i < graph.numVertices; i++) {
for (int j = 0; j < graph.numVertices; j++) {
if (allPairsDistances[i][k] != INF && allPairsDistances[k][j] != INF) {
if (allPairsDistances[i][k] + allPairsDistances[k][j] < allPairsDistances[i][j]) {
allPairsDistances[i][j] = allPairsDistances[i][k] + allPairsDistances[k][j];
allPairsPaths[i][j] = allPairsPaths[k][j];
}
}
}
}
}
}
// 위상 정렬 (진입 차수 기반 - 인접 리스트 버전) - 인접 정점 탐색 및 진입 차수 계산 부분 변경
void calculateInDegreesAL(AdjacencyListGraph graph, int inDegrees[]) {
for (int i = 0; i < graph.numVertices; i++) {
inDegrees[i] = 0;
}
for (int i = 0; i < graph.numVertices; i++) {
EdgeNode *edge = graph.nodes[i].firstEdge;
while (edge != NULL) {
inDegrees[edge->targetNodeIdx]++; // i -> targetNodeIdx 간선이 존재하면 targetNodeIdx의 진입 차수 증가
edge = edge->nextEdge;
}
}
}
int topologicalSortAL(AdjacencyListGraph graph) {
int inDegrees[MAX_NODES];
calculateInDegreesAL(graph, inDegrees); // 인접 리스트 버전 진입 차수 계산
Queue q;
initQueue(&q);
for (int i = 0; i < graph.numVertices; i++) {
if (inDegrees[i] == 0) {
enqueue(&q, i);
}
}
int count = 0;
while (!isEmpty(&q)) {
int current = dequeue(&q);
sortedOrder[count++] = current;
EdgeNode *edge = graph.nodes[current].firstEdge;
while (edge != NULL) {
int neighbor = edge->targetNodeIdx;
inDegrees[neighbor]--;
if (inDegrees[neighbor] == 0) {
enqueue(&q, neighbor);
}
edge = edge->nextEdge;
}
}
return count == graph.numVertices;
}
// DFS 기반 위상 정렬 (인접 리스트 버전) - 인접 정점 탐색 부분 변경
void dfsTopoUtilAL(AdjacencyListGraph graph, int currentNodeIdx) {
dfsVisited[currentNodeIdx] = 1;
EdgeNode *edge = graph.nodes[currentNodeIdx].firstEdge;
while (edge != NULL) {
int neighbor = edge->targetNodeIdx;
if (!dfsVisited[neighbor]) {
dfsTopoUtilAL(graph, neighbor);
}
edge = edge->nextEdge;
}
dfsStack[stackTop++] = currentNodeIdx;
}
int dfsTopologicalSortAL(AdjacencyListGraph graph) {
for (int i = 0; i < graph.numVertices; i++) {
dfsVisited[i] = 0;
}
stackTop = 0;
for (int i = 0; i < graph.numVertices; i++) {
if (!dfsVisited[i]) {
dfsTopoUtilAL(graph, i);
}
}
for (int i = 0; i < graph.numVertices; i++) {
sortedOrder[i] = dfsStack[graph.numVertices - 1 - i];
}
return 1;
}
최소 신장 트리 (Minimum Spanning Tree, MST)
최소 신장 트리는 연결된 가중치 무방향 그래프의 모든 정점을 포함하면서 간선 가중치의 합이 최소가 되는 트리를 찾는 문제입니다. 그래프의 사이클을 만들지 않으면서 모든 정점을 연결하는 최소 비용의 서브그래프를 만듭니다. 주로 프림(Prim) 알고리즘과 크루스칼(Kruskal) 알고리즘이 사용됩니다.
프림 알고리즘 (Prim's Algorithm)
프림 알고리즘은 하나의 시작 정점에서 MST를 점진적으로 확장해 나가는 방식으로 동작합니다. MST에 포함된 정점 집합에서 가장 가까운 (가중치가 가장 작은) 외부 정점을 하나씩 선택하여 MST에 추가합니다.
동작 과정:
- 임의의 시작 정점을 선택하여 MST에 포함시키고, 이 정점과 연결된 모든 간선들을 `min_cost` 배열에 저장합니다.
- MST에 아직 포함되지 않은 정점들 중에서 `min_cost` 값이 가장 작은 정점 `U`를 선택합니다.
- `U`를 MST에 추가하고, `U`와 인접한 모든 정점 `V`에 대해 `min_cost[V]`를 `(U, V)` 간선의 가중치와 현재 `min_cost[V]` 값 중 더 작은 값으로 갱신합니다. (즉, `U`를 통해 `V`로 가는 경로가 더 짧으면 업데이트)
- 모든 정점이 MST에 포함될 때까지 2-3단계를 반복합니다.
프림 알고리즘은 모든 정점들을 포함해야 하므로, 연결 그래프에서만 유효하며, 간선이 많은 밀집(dense) 그래프에 더 효율적입니다.
크루스칼 알고리즘 (Kruskal's Algorithm)
크루스칼 알고리즘은 그래프의 모든 간선들을 가중치 기준으로 정렬한 후, 가장 작은 가중치의 간선부터 하나씩 MST에 추가하는 방식입니다. 이때 사이클이 형성되지 않도록 유니온-파인드(Union-Find) 자료구조를 사용하여 관리합니다.
동작 과정:
- 모든 간선을 가중치에 따라 오름차순으로 정렬합니다.
- 정렬된 간선 리스트에서 가장 작은 가중치의 간선부터 차례대로 선택합니다.
- 선택된 간선이 연결하는 두 정점이 아직 같은 집합(연결 요소)에 속하지 않는다면, 이 간선을 MST에 추가하고 두 정점을 하나의 집합으로 합칩니다 (Union 연산).
- 모든 정점이 하나의 연결 요소가 되거나, 선택할 수 있는 간선이 없을 때까지 2-3단계를 반복합니다.
크루스칼 알고리즘은 간선이 적은 희소(sparse) 그래프에 더 효율적입니다.
임계 경로 (Critical Path)
임계 경로 문제는 방향 비순환 그래프(DAG)에서 특정 프로젝트의 완료 시간을 결정하는 가장 긴 경로를 찾는 문제입니다. AOV(Activity On Vertex) 또는 AOE(Activity On Edge) 네트워크에서 주로 다루며, 각 활동(간선)에 소요 시간이 부여됩니다. 임계 경로는 프로젝트 지연에 가장 민감한 활동들로 구성된 경로입니다.
임계 경로를 찾기 위해서는 각 사건(정점)의 가장 빠른 발생 시간 (Earliest Event Time, EE)과 가장 늦은 발생 시간 (Latest Event Time, LE)을 계산해야 합니다. 또한, 각 활동(간선)의 가장 빠른 시작 시간 (Earliest Start Time, ES)과 가장 늦은 시작 시간 (Latest Start Time, LS)을 계산합니다.
- EE (ve) 계산: 소스(Source, 진입 차수 0) 정점에서 시작하여 모든 정점의 EE를 계산합니다.
ve[j] = max(ve[i] + weight(<i,j>)) - LE (vl) 계산: 싱크(Sink, 진출 차수 0) 정점에서 시작하여 모든 정점의 LE를 계산합니다.
vl[i] = min(vl[j] - weight(<i,j>)) - ES (e) 계산: 각 활동 <i,j>에 대해
e(<i,j>) = ve[i] - LS (l) 계산: 각 활동 <i,j>에 대해
l(<i,j>) = vl[j] - weight(<i,j>)
활동의 여유 시간(Slack)은 l(<i,j>) - e(<i,j>)로 계산됩니다. 여유 시간이 0인 활동들이 임계 활동(Critical Activity)이며, 이들로 구성된 경로가 임계 경로입니다. 임계 경로는 프로젝트의 총 소요 시간을 결정하며, 이 경로상의 어떤 활동이라도 지연되면 프로젝트 전체가 지연됩니다.
알고리즘 시간 복잡도 분석
주요 그래프 알고리즘의 시간 복잡도는 그래프의 표현 방식(인접 행렬 또는 인접 리스트)과 정점의 수(V 또는 n), 간선의 수(E 또는 e)에 따라 달라집니다.
일반적인 연산
- 간선 존재 여부 확인 (u,v):
- 인접 행렬: O(1)
- 인접 리스트: O(deg(u)) (u의 차수), 최악 O(V)
- 정점 u의 모든 인접 간선 찾기:
- 인접 행렬: O(V) (u의 행 전체 스캔)
- 인접 리스트: O(deg(u))
- 정점 삽입:
- 인접 행렬: O(1) (새로운 행/열 추가 없이 마지막에 삽입 시) 또는 O(V^2) (재구조화 필요 시)
- 인접 리스트: O(1)
- 정점 삭제 (u):
- 인접 행렬: O(V) (u의 행과 열 0으로 초기화 또는 이동)
- 인접 리스트: O(V+E) (모든 리스트를 탐색하여 u를 가리키는 간선 제거)
그래프 탐색
- BFS:
- 인접 행렬: O(V^2)
- 인접 리스트: O(V+E)
- DFS:
- 인접 행렬: O(V^2)
- 인접 리스트: O(V+E)
최단 경로 알고리즘
- BFS 기반 (가중치 없는 그래프):
- 인접 행렬: O(V^2)
- 인접 리스트: O(V+E)
- 다익스트라 알고리즘 (단일-소스 최단 경로):
- 인접 행렬: O(V^2)
- 인접 리스트 (우선순위 큐 사용): O(E log V) 또는 O(E + V log V)
- 플로이드-워셜 알고리즘 (모든 쌍 최단 경로):
- 인접 행렬: O(V^3)
- 인접 리스트: O(V^3) (간선 가중치 조회 시 오버헤드 발생 가능)
최소 신장 트리
- 프림 알고리즘:
- 인접 행렬: O(V^2) (간선이 많은 밀집 그래프에 적합)
- 인접 리스트 (우선순위 큐 사용): O(E log V) 또는 O(E + V log V)
- 크루스칼 알고리즘:
- O(E log E) (간선 정렬 시간 포함), 주로 유니온-파인드와 함께 사용
- 간선이 적은 희소 그래프에 적합
위상 정렬
- 진입 차수 기반:
- 인접 행렬: O(V^2)
- 인접 리스트: O(V+E)
- DFS 기반:
- 인접 행렬: O(V^2)
- 인접 리스트: O(V+E)