본문 바로가기

성우리뷰

1260)dfs bfs

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

#define TRUE 1
#define FALSE 0
#define MAX 1001

int arr[MAX][MAX] = { 0, };
int visit[MAX] = { FALSE, };
int queue[MAX];

//int isEmpty()
//{
// if (front == back)
// return TRUE;
// else
// return FALSE;
//}

//void addque(int value)
//{
// back = (back + 1) % MAX;
// queue[back] = value;
//}

//int delque()
//{
// front = (front + 1) % MAX;
// return queue[front];
//}

//int seek()
//{
// return queue[(front+1)%100];
//}

void bfs(int start, int number) {
	int front = 0, back = 0;
	int pop;

	queue[0] = start;
	back++;
	printf("%d ", start);
	visit[start] = TRUE;

	while (front<back){
		pop = queue[front];
		front++;

		for (int i = 1; i <= number; i++) {
			if (arr[pop][i] && !visit[i]) {
				printf("%d ", i);
				queue[back] = i;
				back++;
				visit[i] = TRUE; 
            }
		}
	}
}

void dfs(int start, int number) {
	visit[start] = TRUE;
	printf("%d ", start);

	int i = 0; 

	for (i = 1; i <= number; i++)
		if (arr[start][i] > 0 && !visit[i])
			dfs(i, number);

		if (i == number)
			return;
}

void init(int * visit, int number) {
	for (int i = 0; i <= number; i++)
	visit[i] = FALSE;
}

int main() {
	int number, edge, start;
	scanf_s("%d %d %d", &number, &edge, &start);

	int from, to;
	for (int i = 0; i < edge; i++){
		scanf_s("%d %d", &from, &to);
		arr[from][to] = 1;
		arr[to][from] = 1;
	}

	dfs(start, number);
	init(visit, number);
	printf("\n");
	bfs(start, number);

	return 0;
}

 

///////////////////////////

원형큐는 주석형태로

'성우리뷰' 카테고리의 다른 글