신장 트리

신장 트리(Spanning Tree)

• 연결된 그래프에서 모든 정점을 포함하며, 사이클이 없는 부분 그래프이다.

 

 

 

신장 트리의 주요 특징

• 모든 정점 포함 : 신장 트리는 원래 그래프의 모든 정점을 포함한다.
• 사이클 없음 : 신장 트리는 사이클이 없어야 한다. 이는 신장 트리가 트리의 정의를 따르기 때문이다.
• 간선 수 : 그래프의 정점 수가 n일 때, 신장 트리는 정확히 n−1개의 간선을 가진다. 이는 모든 트리가 가지는 기본적인 성질이다.
• 유일성 : 신장 트리는 항상 유일하지는 않다. 하나의 그래프에는 여러 개의 신장 트리가 존재할 수 있다.
• 이러한 특성 때문에 신장 트리는 네트워크 설계, 알고리즘, 그리고 다양한 컴퓨터 과학 분야에서 중요하게 활용된다.

 

 

 

신장 트리를 찾는 알고리즘

1. 깊이 우선 탐색(DFS, Depth-First Search)

• DFS를 사용하여 그래프를 탐색하면서 방문하는 간선들을 선택하면 신장 트리를 생성할 수 있다.
• DFS는 그래프의 깊은 부분을 우선적으로 탐색하는 방식으로 작동한다.

2. 너비 우선 탐색(BFS, Breadth-First Search)

• BFS를 사용하면 또 다른 형태의 신장 트리를 생성할 수 있다.
• BFS는 그래프의 넓은 부분을 우선적으로 탐색하는 방식으로 작동하며, 각 단계에서 가장 가까운 노드를 먼저 방문한다.