[알고리즘] Graph (5) - Breadth first search(BFS)

[5. BFS, 너비우선탐색]

1. BFS

(1) BFS 기본 전략

  → vertex v를 방문할 시

  → 인접한 모든 vertex를 방문한 것으로 표시

  → queue에 vertex를 추가

  → BFS 구현

#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<int> edge[10001];
bool visit[10001];

void initVisit() {
	for (int i = 0; i < 10001; i++)
		visit[i] = 0;
}
void BFS(int s) {
	queue<int> q;
	int u;

	q.push(s);
	visit[s] = 1;
	while (!q.empty()) {
		u = q.front();
		q.pop();
		printf("%d ", u);
		for (int i = 0; i < edge[u].size(); i++) {
			if (visit[edge[u][i]] == 0) {
				visit[edge[u][i]] = 1;
				q.push(edge[u][i]);
			}
		}
	}
}

int main() {
	initVisit();

	FILE* fp = fopen("graph.txt", "r+t");
	int v, e, s, u, w;
	fscanf(fp, "%d %d %d", &v, &e, &s);	//v=개체의 개수, e=간선의 개수, s=시작점
	for (int i = 0; i < e; i++) {
		fscanf(fp, "%d %d", &u, &w);	//개체간 간선
		edge[u].push_back(w);
		edge[w].push_back(u);
	}
	for (int i = 1; i <= v; i++)
		sort(edge[i].begin(), edge[i].end());
	/* 그래프 확인
	for (int i = 0; i < v; i++) {
		printf("[%d]", i);
		for (int j = 0; j < edge[i].size(); j++)
			printf("->%d, ", edge[i][j]);
		printf("\n");
	}*/
	BFS(s);
}

  → 시간복잡도 : O(v+e)

 

(2) DFS와의 비교

  → 가능한 연결된 모든 노드들을 모두 방문

  → recursive call 사용

  → stack 활용

 

2. 다익스트라 

  → 방향가중치 그래프의 한 개체에서 다른 개체로 통하는 가장 짧은 경로를 찾는 것에 활용

  → 만약 개체 u에서 개체 v로 가고자 할 때

  → u->v, u->w->v 와 같이 두 가지 경로가 있다면

  → 최단 경로 = min{ dist[v], dist[w]+l(w, v) }

Ex)

  → dist[u] : 시작점 A에서 개체 u까지의 거리

  → l(u, v) : 개체 u에서 v까지의 거리

  → dist[C] = min { dist[C], dist[B]+l(B, C) } = min {2, 4+3} = 2

  → dist[B] = min { dist[B], dist[C]+l(C, B) } = min {4, 2+1} = 3

  → dist[D] = min { dist[B]+l(B, D), dist[C]+l(C, B)+l(B, D), dist[C]+l(C, E)+l(E, D) } = min {4+2, 2+1+2, 2+5+1} = 5

  → dist[E] = min { dist[B]+l(B, C)+l(C, E), dist[B]+l(B, E), dist[C]+l(C, B)+l(B, E), dist[C]+l(C, E) } = min {4+3+5, 4+3, 2+1+3, 2+5} = 6

  → 시간복잡도

2. Bellman-Ford algorithm

  → 다익스트라 알고리즘에서 negative edge를 가지는 그래프의 최단경로 찾기

  → 시간복잡도 : O(n*m) (최악 : O(n³))

 

3. All pairs shortest path (Floyd's algorithm)

  → 모든 개체간의 가장 짧은 경로를 찾는 문제

  → 모든 개체에서 다익스트라 알고리즘 실행

  → negative edge허용, negative cycle 비허용

  → Aⁿ[i][j] = min { Aⁿ-¹[i][j], Aⁿ-¹[i][k]+Aⁿ-¹[k][j] }

  → 시간복잡도 : O(n³)

Ex)