Post

트리순회, BFS, DFS

Algorithm Theory

Posted
views 5 min read
Preview Image
트리순회, BFS, DFS

트리 순회 Tree Traversal

개념

트리 구조에서 각각의 노드를 정확히 한 번만, 체계적인 방법으로 방문하는 과정을 말한다.

노드를 방문하는 순서에 따라 전위 순회, 중위 순회, 후위 순회, 레벨 순회로 나눌 수 있다.


전위 순회 Preorder Traversal

먼저 자신의 노드를 방문한 후, 자식의 노드를 방문한다.

DFS 로 구현한다.

  • 루트 → 왼쪽 → 오른쪽

Pseudo Code 

1
2
3
4
5

preorder( node )
    if (node.visited == false)
        node.visited = true
        preorder( node->left )
        preorder( node->right )


중위 순회 Inorder Traversal

왼쪽 노드를 먼저 방문하고, 다음 자신의 노드를 방문 한 뒤 오른쪽 노드를 방문한다.

DFS 로 구현한다.

  • 왼쪽 → 루트 → 오른쪽

Pseudo Code 

1
2
3
4
5

inorder( node )
    if (node.visited == false)
        inorder( node->left )
        node.visited = true
        inorder( node->right )


후위 순회 Postorder Traversal

자식들 노드를 모두 방문한 뒤 마지막으로 루트를 방문한다.

DFS 로 구현한다.

  • 왼쪽 → 오른쪽 → 루트

Pseudo Code 

1
2
3
4
5

postorder( node )
    if (node.visited == false)
        postorder( node->left )
        postorder( node->right )
        node.visited = true


레벨 순회 Level Traversal

트리의 노드를 위에서 아래로, 왼쪽에서 오른쪽으로 순서대로 탐색하는 방식이다.

즉, 같은 깊이의 노드들을 먼저 탐색한다.

BFS 로 구현한다.


개념

어떤 정점에서 시작해 다음 깊이(레벨)의 정점으로 이동하기전,

현재 깊이의 모든 정점을 탐색하며 방문한 정점은 다시 방문하지 않는다.

같은 가중치를 가진 그래프에서 최단거리/최소이동/최소시간 알고리즘으로 쓰인다.


Example Code 

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

#include <bits/stdc++.h>

using namespace std;

vector<int> adj[100];
int visited[100];

int nodeList[] = {10, 12, 14, 16, 18, 20, 22, 24};

void BFS(int here)
{
    queue<int> q;
    visited[here] = 1;
    q.push(here);
    while (q.size())
    {
        int here = q.front();
        q.pop();
        for (int there : adj[here])
        {
            if (visited[there])
                continue;
            visited[there] = visited[here] + 1;
            q.push(there);
        }
    }
}
int main()
{
    adj[10].push_back(12);
    adj[10].push_back(14);
    adj[10].push_back(16);
    adj[12].push_back(18);
    adj[12].push_back(20);
    adj[20].push_back(22);
    adj[20].push_back(24);

    BFS(10);
    for (int i : nodeList)
    {
        cout << i << " : " << visited[i] << '\n';
    }
    cout << "The shortest distance from 10 to 24 is : "
                                    << visited[24] - 1 << '\n';
    return 0;
}

Output 

1
2
3
4
5
6
7
8
9

10 : 1
12 : 2
14 : 2
16 : 2
18 : 3
20 : 3
22 : 4
24 : 4
The shortest distance from 10 to 24 is : 3


개념

어떤 정점부터 시작해 인접한 노드들을 재귀적으로 방문하며 방문한 정점은

다시 방문하지 않으며 각 분기마다 가능한 가장 멀리 있는 정점까지 탐색하는 알고리즘이다.

모든 경로, 조합을 탐색해야할 때, 백트래킹이 필요할 때 사용한다.


Example Code 

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

#include <bits/stdc++.h>

using namespace std;

const int n = 6;

vector<int> adj[n];
int visited[n];

void DFS(int u)
{
    visited[u] = 1;
    cout << u << "\n";
    for (int v : adj[u])
    {
        if (visited[v] == 0)
        {
            DFS(v);
        }
    }
    cout << "The Function is finished from " << u << '\n';
    return;
}
int main()
{
    adj[1].push_back(2);
    adj[1].push_back(3);
    adj[2].push_back(4);
    adj[4].push_back(2);
    adj[2].push_back(5);
    DFS(1);
}


Output 

1
2
3
4
5
6
7
8
9
10

1
2
4
5
3
The Function is finished from 4
The Function is finished from 5
The Function is finished from 2
The Function is finished from 3
The Function is finished from 1
Theory, Algorithm
Cpp Algorithm Coding Test