BFS 너비 우선 탐색 알고리즘

개념

 

BFS와 DFS를 트리 형태로 봤을 때 다음과 같은 동작 과정을 보인다.

출처 : https://velog.io/@newnormal21/DFS-BFS-DP-%EA%B0%9C%EB%85%90

BFS를 그래프 형태에서 보면 다음과 같다.

출처 : https://gmlwjd9405.github.io/2018/08/15/algorithm-bfs.html

BFS(Breadth-First Search)는 너비 우선 탐색으로 기준 노드와 거리를 기준으로 가까운 노드들을 탐색하는 방법이다.

DFS 알고리즘은 모든 노드를 방법하는 방식이였는데 BFS는 두 노드 사이에 최단 경로를 가고 싶을 때 혹은 임의의 경로로 가고 싶을 때 선택하는 알고리즘이다. 

BFS는 DFS에 비해 검색 속도가 더 빠르고 더 복잡하다.

 

BFS는 방문한 노드들을 차례대로 저장하고 꺼낼 수 있는 자료구조인 큐를 사용한다.(FIFO 선입선출)

(DFS는 스택 구조를 사용한다. 스택은 FILO 선입후출이다.)

Prim알고리즘 Dijkstra알고리즘과 유사하다.

 

시간복잡도

>인접행렬을 이용할 경우

O(V^2)

>인접리스트를 이용할 경우

O(V+E)

V : 정점의 개수  E : 간선의 개수

 

 

C언어 코드 (인접 행렬 사용)

#include<stdio.h>
#include<string.h>
#define MAX 1005
int arr[MAX][MAX];
int visit[MAX] = { 0 };

typedef struct Queue {
	int front, rear;
	int data[MAX];
}queue;

void BFS(int v, int n) {
	int cur;
	queue q;
	q.front = 0;
	q.rear = 0;

	visit[v] = 1;
	q.data[q.rear] = v; //enqueue v
	q.rear++;

	while (q.front < q.rear) {
		cur = q.data[q.front]; //dequeue 
		q.front++;
		printf("%d ", cur);

		for (int i = 1; i <= n; i++) {
			if (arr[cur][i] && visit[i] == 0) {
				visit[i] = 1;
				q.data[q.rear] = i; //enqueue i
				q.rear++;
			}
		}
	}
}

int main(void) {
	int n, m, v;//정점개수, 간선개수, 시작정점
	int x, y;

	scanf("%d %d %d", &n, &m, &v);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		arr[x][y] = 1;
		arr[y][x] = 1;
	}
	BFS(v, n);
}

 

 

DFS 최단경로 알고리즘(미완성)

#include<stdio.h>
#include<string.h>
#define MAX 1005
int arr[MAX][MAX];
int distance[MAX] = { 0 };
int parent[MAX]={0};
typedef struct Queue {
	int front, rear;
	int data[MAX];
}queue;

void BFS(int v, int n) {
	int cur;
	queue q;
	q.front = 0;
	q.rear = 0;

	distance[v] = 0;
	parent[v]= v;
	q.data[q.rear] = v; //enqueue v
	q.rear++;

	while (q.front < q.rear) {
		cur = q.data[q.front]; //dequeue 
		q.front++;
		//printf("%d ", cur);
		for (int i = 1; i <= n; i++) {
			if (arr[cur][i] && distance[i] == 0) {
				distance[i]=distance[i]+1;
				parent[i]=cur;
				q.data[q.rear] = i; //enqueue i
				q.rear++;
			}
		}
	}
}

void ShortestPath(int v,int n){
	int path[n];
	
	while(parent[v]!=v){
		v = parent[v];
		// ---path에 v 추가---
	}
	// ---path 뒤집기---
}

int main(void) {
	int n, m, v;//정점개수, 간선개수, 시작정점
	int x, y;

	scanf("%d %d %d", &n, &m, &v);
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &x, &y);
		arr[x][y] = 1;
		arr[y][x] = 1;
	}
	BFS(v, n);
	ShortestPath(v,n);
}