입력 코드
#include <stdio.h>
#define MAX_VERTICES 1001
int DFS_V[MAX_VERTICES] = { 0, }; //DFS를 실행하면서 방문한 정점을 표시하기 위한 배열
int BFS_V[MAX_VERTICES] = { 0, }; //BFS를 실행하면서 방문한 정점을 표시하기 위한
int graph[MAX_VERTICES][MAX_VERTICES] = { 0, };
int queue[MAX_VERTICES];
void dfs(int v, int vertices);
void bfs(int v, int vertices);
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;
}
void dfs(int v, int vertices) {
int w;
DFS_V[v] = 1;
printf("%d ", v);
for (w = 1; w <= vertices; w++) {
if (graph[v][w] == 1 && DFS_V[w] == 0) {
dfs(w, vertices);
}
}
}
void bfs(int v, int vertices) {
int w;
int front, rear, pop;
front = rear = 0;
printf("%d ", v);
BFS_V[v] = 1;
queue[0] = v; rear++;
while (front < rear) {
pop = queue[front]; front++;
for (w = 1; w <= vertices; w++) {
if (graph[pop][w] == 1 && BFS_V[w] == 0) {
printf("%d ", w);
queue[rear] = w; rear++;
BFS_V[w] = 1;
}
}
}
}
코드 설명
#그래프이론 #그래프탐색 #너비우선탐색 #깊이우선탐색
참고
문제 출처
'C' 카테고리의 다른 글
#82. [백준_C언어] 2178 : 미로 탐색 \ 그래프 탐색 (0) | 2021.02.17 |
---|---|
#81. [백준_C언어] 1697 : 숨바꼭질 \ 그래프 이론 (0) | 2021.02.16 |
#79. [백준_C언어] 11399 : ATM \ 정렬 (0) | 2021.02.15 |
#78. [백준_C언어] 2220 : 힙 정렬 \ 정렬 (0) | 2021.02.15 |
#77. [백준_C언어] 11004 : K번째 수 \ 정렬 (0) | 2021.02.13 |