깊이우선탐색(DFS)와 너비우선탐색(BFS) C언어 코드

2023.02.27  최초 작성

 

 

백준 1260 문제 : DFS와 BFS

 

#include <stdio.h>
#define MAX 1001
int graph[MAX][MAX] = { 0, };
int visit_dfs[MAX] = { 0, };
int visit_bfs[MAX] = { 0, };
int queue[MAX];

void dfs(int v, int vertices) {
    visit_dfs[v] = 1;
    printf("%d ", v);
    for (int i = 1; i <= vertices; i++) {
        if (graph[v][i] == 1 && visit_dfs[i] == 0) {
            dfs(i, vertices);
        }
    }
}

void bfs(int v, int vertices) {
    int front, rear, pop;
    front = rear = 0;
    printf("%d ", v);
    visit_bfs[v] = 1;
    queue[0] = v;
    rear++;
    while (front < rear) {
        pop = queue[front];
        front++;
        for (int i = 1; i <= vertices; i++) {
            if (graph[pop][i] == 1 && visit_bfs[i] == 0) {
                printf("%d ", i);
                queue[rear] = i;
                rear++;
                visit_bfs[i] = 1;
            }
        }
    }
}

int main() {
    int vertices, edges, vertex, i, j;
    scanf("%d %d %d", &vertices, &edges, &vertex);

    while (edges--) {
        scanf("%d %d", &i, &j);
        graph[i][j] = 1;
        graph[j][i] = 1;
    }

    dfs(vertex, vertices);
    printf("\n");
    bfs(vertex, vertices);

    return 0;
}

[입력 데이터]

5 5 3
5 4
5 2
1 2
3 4
3 1

[실행 결과]

3 1 2 5 4
3 1 4 2 5

 

 

728x90

반응형