DFS

C++언어를 사용하고 2가지 방식을 이용하여 DFS를 구현했다.

  1. 재귀호출방식(인접행렬, 인접리스트)
  2. 스택방식

방문순서 : A - B - D - E - C -F

       A
     /  |
    B   C
   /   / |
  D - E  F

밑의 코드에서

visited[i]는 i노드에 방문했는지 여부를 아는 변수다.

adjacent는 0부터 시작한다.

입력방식

vertex갯수
edge갯수
start_vertex dest_vertex
....

재귀호출방식

인접행렬


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


int v_size;//vertex 갯수
vector<vector<int>> adjacent; //인접행렬
vector<bool> visited(v_size+1, false);

void dfs(int here)
{
	cout << "visit : " << here << endl;
	visited[here] = true;

	for (int i = 1; i < v_size+1; i++)
	{
		if (adjacent[here][i] != 0 && !visited[i])
			dfs(i);
	}
}

void dfsall() {
	//그래프가 여러개일수 있으므로 모든 정점에 대해 수행

	visited = vector<bool>(v_size+1, false);
	for (int i = 1; i < v_size+1; i++)
	{
		if (!visited[i])
			dfs(i);
	}
}
int main()
{
	cin >> v_size;
	adjacent = vector<vector<int>>(v_size+1, vector<int>(v_size+1, 0));
	
	int e_size;
	cin >> e_size;

	int s, d;
	for (int i = 0; i < e_size; i++)
	{
		cin >> s >> d;
		adjecant[s][d] = 1;
	}
	dfsall();

	return 0;
}

인접행렬

​ 0 1 2 3 4 5 6

0 0 0 0 0 0 0 0

1 0 0 1 1 0 0 0

2 0 0 0 0 1 1 0

3 0 0 0 0 0 0 1

4 0 0 0 0 0 0 0

5 0 0 0 0 0 0 1

6 0 0 0 0 0 0 0

idx 0은 사용하지 않았다.

인접리스트

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


int v_size;//vertex 갯수
vector<vector<int>> adjacent; //인접리스트
vector<bool> visited(adjacent.size(), false);

void dfs(int here)
{
	cout << "visit : " << here << endl;
	visited[here] = true;
	for (int i = 0; i <adjacent[here].size(); i++)
	{
		if (!visited[adjacent[here][i]])
			dfs(adjacent[here][i]);
	}
}

void dfsall() {
	//그래프가 여러개일수 있으므로 모든 정점에 대해 수행

	visited = vector<bool>(adjacent.size(), false);
	for (int i = 1; i < adjacent.size(); i++)
	{
		if (!visited[i])
			dfs(i);
	}
}
int main()
{
	cin >> v_size;
	adjacent = vector<vector<int>>(v_size+1);
	
	int e_size;
	cin >> e_size;

	int s, d;
	for (int i = 0; i < e_size; i++)
	{
		cin >> s >> d;
		adjacent[s].push_back(d);
	}
	
	//인접리스트 출력
	cout << endl<<"-----인접 리스트-----" << endl;
	for (int i = 1; i < adjacent.size(); i++)
	{
		cout << i << " :";
		for (int j=0; j<adjacent[i].size();j++)
		{
			cout << adjacent[i][j]<< " ";
		}
		cout << endl;
	}

	cout << "-----방문순서-----" << endl;
	dfsall();

	return 0;
}

인접리스트 1 : 2 3 2 : 4 5 3 : 6 4 : 5 : 6 6 :

입력예시

6 //vertex갯수

6 //edge갯수

1 2

1 3

2 4

2 5

3 6

5 6 //edge

Stack 방식

재귀함수에서 함수호출에 대한 overhead를 줄일 수 있다.

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


int v_size;//vertex 갯수
vector<vector<int>> adjacent; //인접리스트
vector<bool> visited(adjacent.size(), false);
stack<int> mem;

void dfs(int start)
{
	int current = start;
	mem.push(current);
	visited[current] = true;
	cout << "visit : " << start << endl;
	
	while (mem.size()) {
		current = mem.top();
		for (int i = 1; i <= v_size; i++)
		{
			if (adjacent[current][i] != 0 && !visited[i])
			{
				current = i;
				mem.push(current);
				visited[current] = true;
				cout << "visit : " << current << endl;
				break;
			}
			else if (i == v_size)
			{
				mem.pop();
			}
		}
	}
}

void dfsall() {
	//그래프가 여러개일수 있으므로 모든 정점에 대해 수행

	visited = vector<bool>(v_size+1, false);
	for (int i = 1; i < v_size+1; i++)
	{
		if (!visited[i])
			dfs(i);
	}
}
int main()
{
	cin >> v_size;
	adjacent = vector<vector<int>>(v_size + 1, vector<int>(v_size + 1, 0));

	int e_size;
	cin >> e_size;

	int s, d;
	for (int i = 0; i < e_size; i++)
	{
		cin >> s >> d;
		adjacent[s][d] = 1;
	}
	dfsall();

	return 0;
}

Stack의변화

1

1 2

1 2 4

1 2 5

1 2 5 6

1 2 5 6 3

참고 : https://algorithms.cf/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B3%B5%EB%B6%802-DFS%EA%B9%8A%EC%9D%B4-%EC%9A%B0%EC%84%A0-%ED%83%90%EC%83%89-C