[자료구조] DFS (Depth First Search) 깊이 우선 탐색
인접 리스트 version
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
// [ ][ ][ ][ ][ ][ ][ ][ ]
// DFS (Depth First Search) 깊이 우선 탐색
struct Vertex
{
// int data;
};
vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;
void CreateGraph()
{
vertices.resize(6);
adjacent = vector<vector<int>>(6);
// 인접 리스트
adjacent[0].push_back(1);
adjacent[0].push_back(3);
adjacent[1].push_back(0);
adjacent[1].push_back(2);
adjacent[1].push_back(3);
adjacent[3].push_back(4);
adjacent[5].push_back(4);
}
// DFS
// Dfs(0)
// - Dfs(1)
// -- Dfs(2)
// -- Dfs(3)
// --- Dfs(4)
void Dfs(int here)
{
// 방문!
visited[here] = true;
cout << "Visited : " << here << endl;
// 인접 리스트 version
// 모든 인접 정점을 순회한다
for (int i = 0; i < adjacent[here].size(); i++)
{
int there = adjacent[here][i];
if (visited[there] == false)
Dfs(there);
}
}
int main()
{
CreateGraph();
visited = vector<bool>(6, false);
Dfs(0);
}
|
cs |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
|
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
// [ ][ ][ ][ ][ ][ ][ ][ ]
// DFS (Depth First Search) 깊이 우선 탐색
struct Vertex
{
// int data;
};
vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;
void CreateGraph()
{
vertices.resize(6);
adjacent = vector<vector<int>>(6);
// 인접 리스트
adjacent[0].push_back(1);
adjacent[0].push_back(3);
adjacent[1].push_back(0);
adjacent[1].push_back(2);
adjacent[1].push_back(3);
adjacent[3].push_back(4);
adjacent[5].push_back(4);
}
// DFS
// Dfs(0)
// - Dfs(1)
// -- Dfs(2)
// -- Dfs(3)
// --- Dfs(4)
void Dfs(int here)
{
// 방문!
visited[here] = true;
cout << "Visited : " << here << endl;
// 인접 리스트 version
// 모든 인접 정점을 순회한다
for (int i = 0; i < adjacent[here].size(); i++)
{
int there = adjacent[here][i];
if (visited[there] == false)
Dfs(there);
}
}
// 끊겨있는 정점들도 체크해줘야 한다.
void DfsAll()
{
visited = vector<bool>(6, false);
for (int i = 0; i < 6; i++)
if (visited[i] == false)
Dfs(i);
}
int main()
{
CreateGraph();
//visited = vector<bool>(6, false);
//Dfs(0);
DfsAll();
}
|
cs |
인접행렬 version
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
#include <iostream>
#include <stack>
#include <queue>
using namespace std;
struct Vertex
{
// int data;
};
vector<Vertex> vertices;
vector<vector<int>> adjacent;
vector<bool> visited;
void CreateGraph()
{
vertices.resize(6);
adjacent = vector<vector<int>>(6);
// 인접 행렬 version
// 모든 인접 정점을 순회한다
adjacent = vector<vector<int>>
{
{ 0, 1, 0, 1, 0, 0},
{ 1, 0, 1, 1, 0, 0},
{ 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 1, 0},
{ 0, 0, 0, 0, 0, 0},
{ 0, 0, 0, 0, 1, 0},
};
}
void Dfs(int here)
{
// 방문!
visited[here] = true;
cout << "Visited : " << here << endl;
for (int there = 0; there < 6; there++)
{
if (adjacent[here][there] == 0) // 갈 길이 없다
continue;
// 아직 방문하지 않은 곳이 있으면 방문한다.
if (visited[there] == false)
Dfs(there);
}
}
// 끊겨있는 정점들도 체크해줘야 한다.
void DfsAll()
{
visited = vector<bool>(6, false);
for (int i = 0; i < 6; i++)
if (visited[i] == false)
Dfs(i);
}
int main()
{
CreateGraph();
DfsAll();
}
|
cs |
'⭐ Programming > 자료구조와 알고리즘' 카테고리의 다른 글
| [자료구조] BFS를 이용한 길찾기 구현 (0) | 2022.10.31 |
|---|---|
| [자료구조] BFS (Breadth First Search) 너비 우선 탐색 (0) | 2022.10.28 |
| [자료구조] BIG-O 표기법, 그래프 기초 (0) | 2022.10.27 |
| [자료구조] Queue 큐 (0) | 2022.07.11 |
| [자료구조] Stack 스택 (0) | 2022.07.11 |