C 언어로 구현하는 그래프 탐색: 인접 리스트와 행렬

C 언어로 그래프를 구현하고 탐색할 때, 효율적인 자료 구조 선택은 성능과 메모리 사용량에 큰 영향을 미칩니다. 본 기사에서는 그래프를 표현하는 두 가지 주요 방법인 인접 리스트와 인접 행렬의 차이점을 설명하고, 이들을 활용한 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS) 구현 방법을 소개합니다. 이를 통해 그래프 탐색의 기본 개념부터 실전 활용까지 폭넓게 이해할 수 있습니다.

그래프 탐색의 기본 개념

그래프 탐색은 그래프라는 자료 구조에서 특정 노드를 방문하거나 경로를 찾는 작업입니다. 이를 통해 그래프의 구조를 이해하고 문제를 해결하는 데 사용됩니다.

그래프란 무엇인가

그래프는 노드(정점)와 노드 간의 연결(간선)으로 구성된 자료 구조입니다. 방향성 여부에 따라 방향 그래프와 무방향 그래프로 나뉘며, 간선에 가중치가 부여되면 가중치 그래프가 됩니다.

그래프 탐색의 유형

깊이 우선 탐색(DFS): 한 경로를 끝까지 탐색한 후 다른 경로로 이동하는 방식입니다.
너비 우선 탐색(BFS): 특정 노드와 가까운 노드부터 차례로 탐색하는 방식입니다.

그래프 탐색의 실세계 응용

지도 탐색: 최단 경로 찾기 및 네트워크 연결 분석
소셜 네트워크 분석: 연결된 사용자 그룹 탐색
문제 해결: 퍼즐이나 게임에서 최적의 해결 경로 찾기

그래프 탐색은 다양한 응용 분야에서 핵심적인 도구로 사용되며, 효율적인 탐색 방법은 문제 해결의 성패를 좌우할 수 있습니다.

인접 리스트와 인접 행렬의 비교

그래프를 구현할 때 가장 널리 사용되는 두 가지 방식은 인접 리스트와 인접 행렬입니다. 각 방식은 데이터 구조와 성능에서 차이가 있으며, 사용 사례에 따라 선택이 달라집니다.

인접 리스트

인접 리스트는 각 노드에 연결된 다른 노드들의 목록을 저장하는 방식입니다.

장점:
메모리 효율적(희소 그래프에서 간선만 저장)
간선 추가와 삭제가 용이
단점:
특정 간선 존재 여부 확인에 O(노드 수) 시간이 필요

사용 예시

소셜 네트워크와 같은 희소 그래프에서 메모리를 절약하며 빠른 탐색이 필요한 경우에 적합합니다.

인접 행렬

인접 행렬은 정점의 연결 상태를 이차원 배열로 나타낸 방식입니다.

장점:
특정 간선 존재 여부를 O(1) 시간에 확인
구현이 간단하고 직관적
단점:
메모리 소모가 큼(밀집 그래프에서만 효율적)
간선 추가와 삭제에 시간이 걸림

사용 예시

완전 그래프와 같이 간선의 수가 노드 수의 제곱에 비례하는 경우에 적합합니다.

비교 표

특징	인접 리스트	인접 행렬
메모리 사용량	O(간선 수)	O(노드 수^2)
간선 존재 여부 확인	O(노드 수)	O(1)
간선 추가/삭제	빠름	느림
구현 복잡도	중간	낮음

두 방식의 선택은 그래프의 특성과 요구 사항에 따라 달라지며, 일반적으로 희소 그래프에서는 인접 리스트를, 밀집 그래프에서는 인접 행렬을 사용하는 것이 효율적입니다.

C 언어로 인접 리스트 구현하기

인접 리스트는 연결 리스트를 사용하여 각 노드의 이웃 노드들을 저장하는 방식으로 구현됩니다. 이를 통해 희소 그래프에서 메모리를 효율적으로 사용할 수 있습니다.

기본 구조

인접 리스트를 구현하려면 각 노드에 연결된 노드 목록을 저장하기 위해 다음과 같은 구조체를 사용합니다.

#include <stdio.h>
#include <stdlib.h>

// 그래프 노드 구조체
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

// 그래프 구조체
typedef struct Graph {
    int numVertices;
    Node** adjLists;  // 각 노드의 인접 리스트
} Graph;

그래프 초기화 함수

그래프를 초기화하고 메모리를 할당하는 함수는 다음과 같습니다.

Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;
    graph->adjLists = (Node**)malloc(vertices * sizeof(Node*));

    for (int i = 0; i < vertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

간선 추가 함수

그래프에 간선을 추가하는 함수는 다음과 같이 구현됩니다.

void addEdge(Graph* graph, int src, int dest) {
    // src에서 dest로의 간선 추가
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    // 무방향 그래프인 경우 dest에서 src로의 간선 추가
    newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = src;
    newNode->next = graph->adjLists[dest];
    graph->adjLists[dest] = newNode;
}

그래프 출력 함수

그래프의 인접 리스트를 출력하여 구조를 확인할 수 있습니다.

void printGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        Node* temp = graph->adjLists[i];
        printf("Vertex %d: ", i);
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

결과

위 코드는 그래프의 인접 리스트를 출력하여 각 노드의 연결 관계를 보여줍니다. 예를 들어, 노드 0은 노드 1과 4에 연결됩니다.

인접 리스트는 메모리를 효율적으로 사용하며, 탐색 알고리즘(DFS, BFS)을 적용하기 위한 기본 구조로 널리 사용됩니다.

C 언어로 인접 행렬 구현하기

인접 행렬은 그래프의 정점 간 연결 상태를 이차원 배열로 나타내는 방식입니다. 밀집 그래프에서 간선의 존재 여부를 빠르게 확인할 수 있는 구조입니다.

기본 구조

그래프의 인접 행렬은 정점 수에 따라 동적으로 크기를 설정할 수 있는 2차원 배열로 구현됩니다.

#include <stdio.h>
#include <stdlib.h>

// 그래프 구조체
typedef struct Graph {
    int numVertices;     // 정점의 수
    int** adjMatrix;     // 인접 행렬
} Graph;

그래프 초기화 함수

그래프를 초기화하고 인접 행렬에 메모리를 동적으로 할당하는 함수는 다음과 같습니다.

Graph* createGraph(int vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = vertices;

    // 인접 행렬 메모리 할당
    graph->adjMatrix = (int**)malloc(vertices * sizeof(int*));
    for (int i = 0; i < vertices; i++) {
        graph->adjMatrix[i] = (int*)malloc(vertices * sizeof(int));
        for (int j = 0; j < vertices; j++) {
            graph->adjMatrix[i][j] = 0;  // 초기값 설정
        }
    }

    return graph;
}

간선 추가 함수

정점 간의 간선을 추가하는 함수는 다음과 같습니다.

void addEdge(Graph* graph, int src, int dest) {
    graph->adjMatrix[src][dest] = 1;  // 간선 추가
    graph->adjMatrix[dest][src] = 1; // 무방향 그래프일 경우 대칭으로 추가
}

그래프 출력 함수

인접 행렬을 출력하여 그래프의 구조를 시각적으로 확인할 수 있습니다.

void printGraph(Graph* graph) {
    for (int i = 0; i < graph->numVertices; i++) {
        for (int j = 0; j < graph->numVertices; j++) {
            printf("%d ", graph->adjMatrix[i][j]);
        }
        printf("\n");
    }
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    printGraph(graph);

    return 0;
}

결과

위 코드는 인접 행렬을 출력하여 각 정점 간 연결 관계를 확인합니다. 예를 들어, 출력 결과의 (0,1)과 (1,0) 위치에 값이 1로 표시되면, 정점 0과 1이 연결된 것을 나타냅니다.

인접 행렬의 특징

빠른 간선 확인: 특정 두 정점 간 연결 여부를 O(1) 시간에 확인 가능
메모리 사용량: O(정점 수^2), 간선이 적은 희소 그래프에서는 비효율적
적합한 응용: 밀집 그래프 또는 연결 관계를 자주 확인해야 하는 경우에 적합

인접 행렬은 구현이 간단하고 직관적이며, 탐색 알고리즘을 효율적으로 구현할 수 있는 기반을 제공합니다.

DFS(깊이 우선 탐색) 구현

깊이 우선 탐색(DFS, Depth-First Search)은 그래프 탐색 알고리즘으로, 한 경로를 가능한 깊이까지 탐색한 후, 다른 경로로 이동합니다. 이 섹션에서는 DFS를 인접 리스트와 인접 행렬을 기반으로 구현하는 방법을 다룹니다.

DFS의 작동 원리

시작 정점을 방문하고 방문 여부를 표시합니다.
현재 정점과 인접한 정점 중 방문하지 않은 정점을 탐색합니다.
더 이상 방문할 정점이 없으면, 이전 정점으로 되돌아갑니다(백트래킹).

DFS 구현: 인접 리스트

인접 리스트 기반 DFS는 연결 리스트를 순회하며 방문 여부를 확인합니다.

#include <stdbool.h>

// 방문 상태를 저장하는 배열
bool* visited;

void DFSList(Graph* graph, int vertex) {
    visited[vertex] = true;
    printf("Visited %d\n", vertex);

    Node* temp = graph->adjLists[vertex];
    while (temp) {
        int connectedVertex = temp->vertex;
        if (!visited[connectedVertex]) {
            DFSList(graph, connectedVertex);
        }
        temp = temp->next;
    }
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // 방문 배열 초기화
    visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }

    // DFS 시작
    DFSList(graph, 0);

    return 0;
}

DFS 구현: 인접 행렬

인접 행렬 기반 DFS는 2차원 배열을 순회하며 간선 정보를 확인합니다.

void DFSMatrix(Graph* graph, int vertex) {
    visited[vertex] = true;
    printf("Visited %d\n", vertex);

    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->adjMatrix[vertex][i] == 1 && !visited[i]) {
            DFSMatrix(graph, i);
        }
    }
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    // 방문 배열 초기화
    visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }

    // DFS 시작
    DFSMatrix(graph, 0);

    return 0;
}

결과

예를 들어, 노드 0에서 시작하여 DFS를 수행한 결과는 다음과 같습니다(그래프의 연결 상태에 따라 순서는 다를 수 있음).

Visited 0  
Visited 1  
Visited 2  
Visited 3  
Visited 4

DFS의 특징

시간 복잡도: O(V + E) (인접 리스트), O(V^2) (인접 행렬)
적용 사례: 경로 탐색, 사이클 검출, 강한 연결 요소 분리 등

DFS는 그래프의 깊은 구조를 탐색하는 데 유용하며, 재귀적 또는 스택 기반으로 구현할 수 있습니다.

BFS(너비 우선 탐색) 구현

너비 우선 탐색(BFS, Breadth-First Search)은 그래프의 특정 정점에서 시작하여 모든 인접 정점을 방문한 뒤, 그 다음 단계의 정점을 탐색하는 방식으로 작동합니다. BFS는 큐 자료 구조를 사용하여 구현되며, 최단 경로 탐색에 유용합니다.

BFS의 작동 원리

시작 정점을 큐에 삽입하고 방문 여부를 표시합니다.
큐에서 정점을 하나 꺼내고, 해당 정점의 인접 정점을 순회하며 방문하지 않은 정점을 큐에 삽입합니다.
큐가 비어 있을 때까지 반복합니다.

BFS 구현: 인접 리스트

인접 리스트 기반 BFS는 각 정점의 연결 리스트를 순회하여 큐에 삽입하는 방식으로 작동합니다.

#include <stdbool.h>
#include <stdlib.h>

// 큐 구현
typedef struct Queue {
    int* items;
    int front;
    int rear;
} Queue;

Queue* createQueue(int size) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->items = (int*)malloc(size * sizeof(int));
    queue->front = -1;
    queue->rear = -1;
    return queue;
}

void enqueue(Queue* queue, int value) {
    queue->items[++queue->rear] = value;
}

int dequeue(Queue* queue) {
    return queue->items[++queue->front];
}

bool isEmpty(Queue* queue) {
    return queue->front == queue->rear;
}

// BFS 알고리즘
void BFSList(Graph* graph, int startVertex) {
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }

    Queue* queue = createQueue(graph->numVertices);
    visited[startVertex] = true;
    enqueue(queue, startVertex);

    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("Visited %d\n", currentVertex);

        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }

    free(visited);
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    BFSList(graph, 0);

    return 0;
}

BFS 구현: 인접 행렬

인접 행렬 기반 BFS는 2차원 배열을 순회하며 연결된 정점을 확인하여 큐에 삽입합니다.

void BFSMatrix(Graph* graph, int startVertex) {
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) {
        visited[i] = false;
    }

    Queue* queue = createQueue(graph->numVertices);
    visited[startVertex] = true;
    enqueue(queue, startVertex);

    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);
        printf("Visited %d\n", currentVertex);

        for (int i = 0; i < graph->numVertices; i++) {
            if (graph->adjMatrix[currentVertex][i] == 1 && !visited[i]) {
                visited[i] = true;
                enqueue(queue, i);
            }
        }
    }

    free(visited);
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 1, 4);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);

    BFSMatrix(graph, 0);

    return 0;
}

결과

노드 0에서 BFS를 시작한 결과는 다음과 같이 출력됩니다(그래프의 연결 상태에 따라 순서는 다를 수 있음).

Visited 0  
Visited 1  
Visited 4  
Visited 2  
Visited 3

BFS의 특징

시간 복잡도: O(V + E) (인접 리스트), O(V^2) (인접 행렬)
적용 사례: 최단 경로 탐색, 연결 요소 확인, 네트워크의 폭발적 확산 시뮬레이션

BFS는 너비를 우선으로 탐색하여 그래프의 구조적 특성을 파악하는 데 효과적입니다.

그래프 탐색 응용 예제

그래프 탐색은 다양한 문제 해결에 직접적으로 활용됩니다. 이 섹션에서는 경로 탐색, 사이클 검출, 최단 경로 문제 등의 응용 사례와 구현 예제를 다룹니다.

응용 1: 경로 탐색

그래프 탐색을 활용하여 두 정점 간 경로가 존재하는지 확인할 수 있습니다.

경로 존재 여부 확인 (DFS 기반)

bool isPathExistDFS(Graph* graph, int start, int end, bool* visited) {
    if (start == end) return true;

    visited[start] = true;
    Node* temp = graph->adjLists[start];

    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            if (isPathExistDFS(graph, adjVertex, end, visited)) {
                return true;
            }
        }
        temp = temp->next;
    }

    return false;
}

bool findPath(Graph* graph, int start, int end) {
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) visited[i] = false;

    bool result = isPathExistDFS(graph, start, end, visited);
    free(visited);
    return result;
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 0, 4);
    addEdge(graph, 1, 2);
    addEdge(graph, 1, 3);

    if (findPath(graph, 0, 3)) {
        printf("Path exists between 0 and 3\n");
    } else {
        printf("No path exists between 0 and 3\n");
    }

    return 0;
}

응용 2: 사이클 검출

그래프에서 사이클이 존재하는지 확인할 수 있습니다.

사이클 검출 (DFS 기반)

bool isCycleDFS(Graph* graph, int vertex, bool* visited, int parent) {
    visited[vertex] = true;
    Node* temp = graph->adjLists[vertex];

    while (temp) {
        int adjVertex = temp->vertex;
        if (!visited[adjVertex]) {
            if (isCycleDFS(graph, adjVertex, visited, vertex)) {
                return true;
            }
        } else if (adjVertex != parent) {
            return true;  // 사이클 존재
        }
        temp = temp->next;
    }

    return false;
}

bool detectCycle(Graph* graph) {
    bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
    for (int i = 0; i < graph->numVertices; i++) visited[i] = false;

    for (int i = 0; i < graph->numVertices; i++) {
        if (!visited[i]) {
            if (isCycleDFS(graph, i, visited, -1)) {
                free(visited);
                return true;
            }
        }
    }

    free(visited);
    return false;
}

실행 예제

int main() {
    Graph* graph = createGraph(5);

    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 2, 0);  // 사이클 존재
    addEdge(graph, 3, 4);

    if (detectCycle(graph)) {
        printf("Cycle detected in the graph\n");
    } else {
        printf("No cycle detected in the graph\n");
    }

    return 0;
}

응용 3: 최단 경로 탐색

BFS를 활용하여 무가중치 그래프에서 최단 경로를 탐색할 수 있습니다.

최단 경로 찾기 (BFS 기반)

void shortestPathBFS(Graph* graph, int start, int end) {
    int* distance = (int*)malloc(graph->numVertices * sizeof(int));
    for (int i = 0; i < graph->numVertices; i++) distance[i] = -1;

    Queue* queue = createQueue(graph->numVertices);
    enqueue(queue, start);
    distance[start] = 0;

    while (!isEmpty(queue)) {
        int currentVertex = dequeue(queue);

        Node* temp = graph->adjLists[currentVertex];
        while (temp) {
            int adjVertex = temp->vertex;
            if (distance[adjVertex] == -1) {  // 방문하지 않은 정점
                distance[adjVertex] = distance[currentVertex] + 1;
                enqueue(queue, adjVertex);

                if (adjVertex == end) {
                    printf("Shortest path length: %d\n", distance[adjVertex]);
                    free(distance);
                    return;
                }
            }
            temp = temp->next;
        }
    }

    printf("No path exists between %d and %d\n", start, end);
    free(distance);
}

실행 예제

int main() {
    Graph* graph = createGraph(6);

    addEdge(graph, 0, 1);
    addEdge(graph, 1, 2);
    addEdge(graph, 0, 3);
    addEdge(graph, 3, 4);
    addEdge(graph, 4, 5);

    shortestPathBFS(graph, 0, 5);

    return 0;
}

결과

경로 탐색, 사이클 검출, 그리고 최단 경로 계산은 다양한 문제 해결에서 핵심 역할을 하며, 각각의 방법은 그래프의 구조와 문제의 특성에 따라 적합하게 선택됩니다.

연습 문제

그래프 탐색 알고리즘의 이해를 심화하기 위해, 다음과 같은 연습 문제를 풀어보세요. 각 문제는 그래프 탐색 및 구현 능력을 향상시키는 데 도움을 줍니다.

문제 1: 두 노드 간 경로 확인

주어진 무방향 그래프에서 두 노드 간 경로가 존재하는지 확인하세요.

입력: 노드 수, 간선 리스트, 두 노드의 번호
출력: 경로 존재 여부(YES 또는 NO)

힌트: DFS나 BFS를 사용해 구현하세요.

예제 입력

노드 수: 5  
간선: (0, 1), (1, 2), (1, 3), (3, 4)  
시작 노드: 0  
종료 노드: 4

예제 출력

YES

문제 2: 사이클 검출

주어진 무방향 그래프에서 사이클이 존재하는지 확인하세요.

입력: 노드 수와 간선 리스트
출력: 사이클 존재 여부(YES 또는 NO)

힌트: DFS 기반으로 부모 노드를 추적하여 구현하세요.

예제 입력

노드 수: 4  
간선: (0, 1), (1, 2), (2, 3), (3, 0)

예제 출력

YES

문제 3: 최단 경로 계산

무가중치 그래프에서 특정 시작 노드와 끝 노드 간의 최단 경로 길이를 계산하세요.

입력: 노드 수, 간선 리스트, 시작 노드, 끝 노드
출력: 최단 경로 길이

힌트: BFS를 사용하여 최단 경로를 계산하세요.

예제 입력

노드 수: 6  
간선: (0, 1), (1, 2), (0, 3), (3, 4), (4, 5)  
시작 노드: 0  
종료 노드: 5

예제 출력

문제 4: 모든 연결 요소 탐색

주어진 무방향 그래프에서 연결 요소의 수를 계산하세요.

입력: 노드 수와 간선 리스트
출력: 연결 요소의 수

힌트: 모든 노드에 대해 DFS나 BFS를 반복적으로 수행하세요.

예제 입력

노드 수: 6  
간선: (0, 1), (1, 2), (3, 4)

예제 출력

문제 5: 그래프 시각화

주어진 그래프를 시각화하세요.

입력: 노드 수와 간선 리스트
출력: 그래프의 인접 리스트 또는 인접 행렬

예제 입력

노드 수: 4  
간선: (0, 1), (1, 2), (2, 3)

예제 출력

인접 리스트:  
0 -> 1  
1 -> 0 -> 2  
2 -> 1 -> 3  
3 -> 2

이 연습 문제를 통해 그래프 탐색 알고리즘을 실습하고, 다양한 그래프 구조를 이해해 보세요. 문제 풀이 후 코드를 실행해 결과를 확인하세요!

요약

본 기사에서는 C 언어를 사용하여 그래프 탐색을 구현하는 방법을 다뤘습니다. 인접 리스트와 인접 행렬의 차이점과 구현 방법, 그리고 DFS와 BFS를 활용한 탐색 알고리즘을 자세히 설명했습니다. 또한 경로 탐색, 사이클 검출, 최단 경로 계산과 같은 실전 응용 사례와 연습 문제를 통해 독자가 그래프 탐색에 대한 이해를 심화할 수 있도록 구성했습니다. 적절한 자료 구조와 알고리즘을 선택하여 그래프 문제를 효율적으로 해결하는 방법을 익혀 보세요.