[자료구조] 그래프 순회(Graph Traversal) 개념 및 구현

1. 그래프 순회

- 그래프 순회란 정점과 에지를 체계적으로 방문하는 것을 말한다.

ⓐ 깊이 우선 탐색(depth first search_DFS) : 전순위 순회 일반화

ⓑ 너비 우선 탐색(Breadth first search_BFS) : 레벨순위 순회 일반화

 

 

2. 깊이 우선 탐색(DFS)

1) 알고리즘

① 먼저 정점 v를 방문 한 다음 

② v에 인접한 정점 중에서 방문하지 않는 정점 w를 찾아서 w에 대한 DFS를 재귀적으로 수행한다.

 

2) 구현

#include <iostream>
#include <vector>
using namespace std;

#define MAX_NODE 100

bool visited[MAX_NODE];
vector<int> v[MAX_NODE];

void DFS(int x){
	visited[x] = true;
	printf("%d ", x);
	for (int i = 0; i < v[x].size(); i++) {
		int next = v[x][i];
		if (!visited[next]) {
			DFS(next);
		}		
	}
}

int main() {
	int node, vertex;
	cout << "노드의 개수와 간선의 개수를 입력하시오 : ";
	cin >> node >> vertex;

	for (int i = 0; i < vertex; i++) {
		int x, y;
		cout << "연결되는 두 노드를 입력하시오 : ";
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	DFS(1);
}

 

- 시간 복잡도 : 𝑂(𝑛 + 𝑚) //n은 정점개수, m은 에지 개수

 

3. 너비 우선 탐색(BFS)

1) 알고리즘

ⓐ 먼저 𝑣를 방문한 후, 𝑣에 인접한 정점을 차례로 방문한다.

ⓑ 다음으로 두 번째 방문한 정점과 인접한 정점을 방문하고, 이후 세 번째 방문한 정점에 인접한 정점을 방문한다.

ⓒ 위 과정을 반복한다.

 

2) 구현

- 각 정점을 방문할 때 그에 인접한 정점을 큐에 삽입하고,  다음으로 방문할 정점은 큐에서 삭제하여 얻는다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

#define MAX_NODE 100

bool visited[MAX_NODE];
vector<int> v[MAX_NODE];
queue<int> q;

void bfs(int st) {
	q.push(st);
	visited[st] = 1;
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		printf("%d ", now);
		for (int i = 0; i < v[now].size(); i++) {
			int next = v[now][i];
			if (!visited[next]) {
				q.push(next);
				visited[next] = 1;
			}
		}
	}
}

int main() {

	int node, vertex;
	cout << "노드의 개수와 간선의 개수를 입력하시오 : ";
	cin >> node >> vertex;

	for (int i = 0; i < vertex; i++) {
		int x, y;
		cout << "연결되는 두 노드를 입력하시오 : ";
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}

	for (int j = 1; j <= node; j++) {
		sort(v[j].begin(), v[j].end());
	}

	bfs(1);
}

- 시간 복잡도 :  𝑂(𝑛 + 𝑚) //n은 정점개수, m은 에지 개수

 

4. 연결성분

- 연결성분이란 서로 연결되어 있는 여러 개의 고립된 부분 그래프 각각을 이야기한다

- dfs와 bfs를 이용하여 구할 수 있다. (dfs/bfs를 몇번 돌았는지)

 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n, m;
vector<int> adj[1002];
bool visited[1002];
void dfs(int now) {
	visited[now] = 1;
	for (int i = 0; i < adj[now].size(); i++){
		int next = adj[now][i];
		if (!visited[next]) dfs(next);
	}
}


int main() {

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		int x, y;
		cin >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
    
	int cnt = 0;
	for (int k = 1; k <= n; k++) {
		if (visited[k]) continue;
		dfs(k);
		cnt++;
	}
	cout << cnt;
}

- 시간 복잡도 :  𝑂(𝑛 + 𝑚)