[C 언어/C++] C 언어 DFS 깊이 우선 탐색 알고리즘 활용 예제(Depth First Search)

 

목차

1. 이전 포스팅의 C 언어 malloc 함수로 메모리 동적 할당 예제 학습 링크
2. 이전 포스팅의 C 언어 TCP 소켓 클라이언트 생성 및 메세지 전송 예제 학습 링크
3. 이전 포스팅의 C 언어 디렉토리 내의 모든 파일 SHA256 해시 값 계산하기 예제 학습 링크
4. C 언어 Depth First Search 알고리즘인 DFS 깊이 우선 탐색 코드 예제
5. C 언어 사용자에게 탐색 노드 값을 입력받아 DFS 탐색으로 노드 순서 찾기 예제

 

 

 

 

 

 

 

 

 

이전 포스팅의 C 언어 malloc 함수로 메모리 동적 할당 예제 학습 링크

이전 포스팅에서는 c언어에서 malloc 함수를 호출하여 개발자가 원하는 만큼의 메모리 공간을 동적으로 할당하는 방법에 대해 알아보았습니다. memory allocation 즉 메모리 할당이란 의미입니다. 보통 int, char 등의 포인터 변수는 4byte, 1byte 등의 메모리 공간을 가리키는 변수입니다. 즉 이 변수들에게 해당 크기 만큼을 표현할 수 있는 공간만 가리킬 수 있습니다. 하지만 malloc 함수에 의해 반환되는 포인터는 내가 원하는 크기 만큼 공간을 생성할 수 있습니다. 따라서 c언어에서 메모리 동적 할당이 필요하시다면 아래 링크의 포스팅을 참고하여 학습해주세요.

 

2023.08.09 - [C] - [C/C++] malloc 메모리 동적 할당 예제(포인터, free)

[C/C++] malloc 메모리 동적 할당 예제(포인터, free)

 

 

 

 

 

 

 

 

 

이전 포스팅의 C 언어 TCP 소켓 클라이언트 생성 및 메세지 전송 예제 학습 링크

다음으로 이전 포스팅에서는 c언어에서 tcp 소켓 클라이언트를 생성하여 상대방에게 tcp 메세지를 전송하는 예제에 대해 알아보았습니다. tcp는 연결지향 프로토콜로서 연결을 확립한 후 메세지를 주고받는 프로토콜입니다. 특히 오류제어, 흐름제어 등의 기능이 포함되어 있어서 메세지 중간 손실이나 유실이 적습니다. 다만 이러한 기능으로인해 속도가 udp보다는 느릴 수 있지만 그 속도 차이는 현재의 네트워크 기술에서는 미미합니다. 만약 c언어로 tcp 소켓 통신 프로그래밍을 하고 계시다면 아래의 포스팅을 참고하여 학습해보세요.

 

2023.08.09 - [C] - [C/C++] TCP 소켓 파일 주고 받기 예제 - 2(fseek, 클라이언트)

[C/C++] TCP 소켓 파일 주고 받기 예제 - 2(fseek, 클라이언트)

 

 

 

 

 

 

 

이전 포스팅의 C 언어 디렉토리 내의 모든 파일 SHA256 해시 값 계산하기 예제 학습 링크

마지막으로 이전 포스팅에서는 c언어에서 사용자가 원하는 특정 디렉토리 내의 모든 파일에 대한 sha256 해시 값을 계산하여 화면에 출력하는 예제를 알아보았습니다. 해시는 파일의 무결성 검사를 위해 많이 사용하는 알고리즘입니다. 또한 해당 포스팅의 예제에서는 모든 파일의 해시값을 구한 후 로컬에 텍스트 파일로 저장하여 이후 파일의 무결성을 검사하기 위한 기능을 추가하였습니다. 만약 c 프로그램으로 파일 무결성 검사 프로그램을 만들고 계시다면 아래 링크를 참고해보세요.

 

2023.08.09 - [C] - [C/C++] 디렉토리 내의 모든 파일 SHA256 해시값 구하기 예제(sha256, openssl)

[C/C++] 디렉토리 내의 모든 파일 SHA256 해시값 구하기 예제(sha256, openssl)

 

 

 

 

 

 

 

C 언어 Depth First Search 알고리즘인 DFS 깊이 우선 탐색 코드 예제

아래는 c언어에서 Depth First Search(DFS) 깊이 우선 탐색 알고리즘을 구현한 예제입니다. 노드들의 값들에서 깊이 우선으로 노드들을 탐색합니다.

 

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* graph[6]; // 정점 수에 맞게 배열 생성

int visited[6] = {0};

// 그래프에 정점 추가
void addNode(int vertex, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = graph[vertex];
    graph[vertex] = newNode;
}

// 깊이 우선 탐색 함수
void dfs(int vertex) {
    printf("%d ", vertex + 1);
    visited[vertex] = 1;

    struct Node* temp = graph[vertex];
    while (temp != NULL) {
        if (!visited[temp->data - 1]) {
            dfs(temp->data - 1);
        }
        temp = temp->next;
    }
}

int main() {
    // 그래프 생성
    addNode(0, 2);
    addNode(0, 3);
    addNode(1, 1);
    addNode(1, 4);
    addNode(1, 5);
    addNode(2, 1);
    addNode(2, 5);
    addNode(3, 2);
    addNode(4, 2);
    addNode(4, 3);
    addNode(4, 6);
    addNode(5, 3);
    addNode(5, 5);

    printf("DFS 결과: ");
    dfs(0); // 시작 노드를 0으로 설정

    return 0;
}

 

c언어에서 DFS 방식으로 그래프를 탐색하는 모습. 탐색하는 노드의 순서이다.

 

 

 

 

 

 

C 언어 사용자에게 탐색 노드 값을 입력받아 DFS 탐색으로 노드 순서 찾기 예제

아래는 c언어에서 DFS 알고리즘으로 사용자가 탐색 시작 노드를 입력하여 그 노드를 기준으로 탐색 노드들을 출력하는 예제입니다.

 

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

struct Node {
    int data;
    struct Node* next;
};

struct Node* graph[6]; // 정점 수에 맞게 배열 생성

int visited[6] = {0};

// 그래프에 정점 추가
void addNode(int vertex, int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->next = graph[vertex];
    graph[vertex] = newNode;
}

// 깊이 우선 탐색 함수
void dfs(int vertex) {
    printf("%d ", vertex + 1);
    visited[vertex] = 1;

    struct Node* temp = graph[vertex];
    while (temp != NULL) {
        if (!visited[temp->data - 1]) {
            dfs(temp->data - 1);
        }
        temp = temp->next;
    }
}

int main() {
    // 그래프 생성
    addNode(0, 2);
    addNode(0, 3);
    addNode(1, 1);
    addNode(1, 4);
    addNode(1, 5);
    addNode(2, 1);
    addNode(2, 5);
    addNode(3, 2);
    addNode(4, 2);
    addNode(4, 3);
    addNode(4, 6);
    addNode(5, 3);
    addNode(5, 5);

    int startNode;
    printf("시작 노드를 입력하세요 (1부터 6까지): ");
    scanf("%d", &startNode);

    if (startNode < 1 || startNode > 6) {
        printf("올바르지 않은 노드입니다.\n");
        return 1; // 에러 코드
    }

    printf("DFS 결과: ");
    dfs(startNode - 1); // 시작 노드를 입력받은 값에서 1을 빼고 전달

    return 0;
}

 

DFS 탐색시 시작 노드를 변경하면 그 시점으로부터 탐색 노드들의 순서가 출력된다.