그래프 탐색: DFS,BFS 트리: inorder, preorder, postorder

preorder = root left right
DFS use stack = inorder= left root right
postorder = left right root
BFS use queue = print each level

그래프

• 소셜 네트워크, 교통 시스템, 컴퓨터 네트워크 등 다양한 현실 세계의 시나리오를 나타내는 데 사용됩니다.
• 노드 또는 정점들이 간선으로 연결된 모음입니다.
• 간선은 노드들 간의 관계나 연결을 나타냅니다.
• 간선은 방향성이 있을 수도, 없을 수도 있습니다.
• 사이클(출발점과 도착점이 같은 경로)이 있을

그래프 용어

• 노드(Node) : 그래프 또는 트리에서 하나의 정점을 뜻합니다. 데이터나 객체 등의 값을 가질 수 있으며, 간선을 통해 다른 노드와 연결됩니다.
• 간선(Edge) : 그래프 또는 트리에서 노드 간의 연결을 나타내는 선을 뜻합니다. 간선은 방향성이 있을 수도, 없을 수도 있습니다.
• 깊이(Depth)란, 노드에서 루트 노드까지 이어진 경로의 길이를 말합니다. 즉, 특정 노드의 깊이는 루트 노드에서부터 그 노드까지 이어진 간선의 수를 의미합니다. 트리에서 루트 노드의 깊이는 0이며, 그 이후부터는 1씩 증가합니다.
• Breadth(너비)는 일반적으로 트리에서 사용되는 용어는 아니지만, 너비 우선 탐색(BFS)에서 사용되는 용어입니다. 노드의 레벨(깊이)마다 해당 노드의 인접 노드들이 "한 번에" 방문되므로, 이를 "너비"라고 표현합니다. 따라서, 너비 우선 탐색에서 "너비"는 트리에서의 노드의 레벨(깊이)을 의미하며, 탐색 순서는 노드의 깊이와는 관련이 없습니다.

예제

순회(traversal) 방법

그래프 순회는 기본적으로 재귀함수에 특화되어 있습니다.

DFS Depth-First Search 깊이 우선 탐색

• 시작 노드 1을 스택에 삽입합니다.
• 스택에는 현재 [1]이 들어 있습니다.
• 스택에서 노드 1을 꺼내어 출력합니다.
• 스택에는 현재 []가 들어 있습니다.
• 노드 1과 연결된 간선 a, b, c를 따라 각각 노드 2, 3, 5를 스택에 삽입합니다.
• 스택에는 현재 [5, 3, 2]가 들어 있습니다.
• 스택에서 노드 2를 꺼내어 출력합니다.
• 스택에는 현재 [5, 3]가 들어 있습니다.
• 노드 2와 연결된 간선 d를 따라 노드 3을 스택에 삽입합니다.
• 스택에는 현재 [5, 3, 3]이 들어 있습니다.
• 스택에서 노드 3을 꺼내어 출력합니다.
• 스택에는 현재 [5, 3]이 들어 있습니다.
• 노드 3과 연결된 간선 e, f를 따라 각각 노드 4, 5를 스택에 삽입합니다.
• 스택에는 현재 [5, 4, 5]가 들어 있습니다.
• 스택에서 노드 5를 꺼내어 출력합니다.
• 스택에는 현재 [4]가 들어 있습니다.
• 노드 5와 연결된 간선 g를 따라 노드 4를 스택에 삽입합니다.
• 스택에는 현재 [4, 4]가 들어 있습니다.
• 스택에서 노드 4를 꺼내어 출력합니다.
• 스택에는 현재 []가 들어 있습니다.
• 스택에서 꺼낼 노드가 없으므로 DFS 탐색을 종료합니다.

BFS Breadth-First Search 너비 우선 탐색

• 시작 노드 1을 큐에 삽입합니다.
• 큐에는 현재 [1]이 들어 있습니다.
• 큐에서 노드 1을 꺼내어 출력합니다.
• 큐에는 현재 []가 들어 있습니다.
• 노드 1과 연결된 간선 a, b, c를 따라 각각 노드 2, 3, 5를 큐에 삽입합니다.
• 큐에는 현재 [2, 3, 5]가 들어 있습니다.
• 큐에서 노드 2를 꺼내어 출력합니다.
• 큐에는 현재 [3, 5]가 들어 있습니다.
• 노드 2와 연결된 간선 d를 따라 노드 3을 큐에 삽입합니다.
• 큐에는 현재 [3, 5, 3]이 들어 있습니다.
• 큐에서 노드 3을 꺼내어 출력합니다.
• 큐에는 현재 [5, 3]이 들어 있습니다.
• 노드 3과 연결된 간선 e, f를 따라 각각 노드 4, 5를 큐에 삽입합니다.
• 큐에는 현재 [5, 3, 4, 5]가 들어 있습니다.
• 큐에서 노드 5를 꺼내어 출력합니다.
• 큐에는 현재 [3, 4, 5]가 들어 있습니다.
• 노드 5와 연결된 간선 g를 따라 노드 4를 큐에 삽입합니다.
• 큐에는 현재 [3, 4, 3]이 들어 있습니다.
• 큐에서 노드 3을 꺼내어 출력합니다.
• 큐에는 현재 [4, 3]이 들어 있습니다.
• 노드 3과 연결된 노드 5는 이미 큐에 삽입되어 있으므로 무시합니다.
• 큐에서 노드 4를 꺼내어 출력합니다.
• 큐에는 현재 [3]이 들어 있습니다.
• 큐에서 노드 3을 꺼내어 출력합니다.
• 큐에는 현재 []가 들어 있습니다.
• 큐에서 꺼낼 노드가 없으므로 BFS 탐색을 종료합니다.

트리

• 파일 시스템, 조직도, 가계도 등과 같은 계층 구조를 나타내는 데 사용됩니다.
• 그래프의 종류중 하나 입니다.
• 어떤 두 노드 간에 하나의 경로만 있습니다.
• 사이클(출발점과 도착점이 같은 경로)이 없습니다.

트리 용어

• 가지(Branch) : 트리에서 루트와 다른 노드를 연결하는 간선과 해당 노드를 뜻합니다. 루트와 다른 노드 사이에는 여러 개의 가지가 존재할 수 있습니다.
• 루트(Root) : 트리에서 가장 위에 있는 노드를 뜻합니다. 모든 다른 노드는 루트에서 시작하는 가지(branch)나 하위 리프 노드(leaf node)에 해당합니다.
• 리프(Leaf) : 트리에서 마지막 노드로, 자식 노드를 가지지 않는 노드를 말합니다. 즉, 더 이상 다른 노드로 확장되지 않는 마지막 노드입니다.
• 부모(Parent) : 트리에서 자식 노드를 가지는 노드를 말합니다. 즉, 자신에게 연결된 간선을 따라 위로 올라가면, 자신보다 상위에 위치한 노드를 의미합니다.
• 자식(Child) : 트리에서 부모 노드에 연결된 하위 노드를 말합니다. 즉, 자신에게 연결된 간선을 따라 아래로 내려가면, 자신보다 하위에 위치한 노드를 의미합니다.

예제

순회(traversal) 방법

Preorder(전위 순회)

Preorder는 루트 노드를 가장 먼저 방문하는 순회 방법입니다. 즉, 루트 노드를 출력한 후 왼쪽 서브 트리를 순회하고, 이어서 오른쪽 서브 트리를 순회합니다. Preorder는 아래와 같은 순서로 노드를 방문합니다.

1. 루트 노드
2. 왼쪽 서브 트리
3. 오른쪽 서브 트리

• 예제: Preorder: 1 2 4 5 8 9 3 6 7

Inorder(중위 순회)

Inorder는 루트 노드를 중간에 방문하는 순회 방법입니다. 즉, 왼쪽 서브 트리를 순회한 후 루트 노드를 출력하고, 이어서 오른쪽 서브 트리를 순회합니다. Inorder는 아래와 같은 순서로 노드를 방문합니다.

1. 왼쪽 서브 트리
2. 루트 노드
3. 오른쪽 서브 트리

• 예제: Inorder: 4 2 8 5 9 1 6 3 7

Postorder(후위 순회)

Postorder는 루트 노드를 가장 마지막에 방문하는 순회 방법입니다. 즉, 왼쪽 서브 트리와 오른쪽 서브 트리를 순회한 후 루트 노드를 출력합니다. Postorder는 아래와 같은 순서로 노드를 방문합니다.

1. 왼쪽 서브 트리
2. 오른쪽 서브 트리
3. 루트 노드

• 예제: Postorder: 4 8 9 5 2 6 7 3 1