[알고리즘] 최소신장트리(MST)와 그래프의 순회(Graph Traversal)

한국어

<h1 id="신장-트리spanning-tree">신장 트리(Spanning Tree)</h1> <p>그래프 내의 모든 정점을 포함하는 트리<br /> 최소 연결 부분 그래프.</p> <p>N개의 정점을 가지는 그래프의 최소 간선의 수는 N-1개이며, N-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 이루어지고 이것이 바로 Spanning Tree라 할 수 있다.</p> <p>하나의 그래프에는 많은 신장 트리가 존재할 수 있으며, 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 <strong>포함해서는 안된다</strong>.</p> <h2 id="최소-신장트리mst--minimum-spanning-tree">최소 신장트리(MST : Minimum Spanning Tree)</h2> <p>가능한 신장트리에서 간선의 가중치 합이 최소인 신장트리를 의미</p> <p>최소 비용 신장 트리를 구하는 방법들은 모두 <strong>탐욕 알고리즘</strong>(Greedy Algorithm)으로 구현</p> <p>** 탐욕 알고리즘 : 각 단계에서 최선의 선택이 최종 단계에서도 최선의 결과를 나타낼 것이라고 생각하는 알고리즘</p> <h2 id="크루스칼-알고리즘kruskals-algorithm">크루스칼 알고리즘(Kruskal’s Algorithm)</h2> <p>간선 위주의 알고리즘.</p> <ol> <li>모든 간선들의 가중치를 오름차순으로 <code class="language-plaintext highlighter-rouge">정렬</code></li> <li>가중치가 <code class="language-plaintext highlighter-rouge">최소</code>인 간선을 선택</li> <li>위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 <code class="language-plaintext highlighter-rouge">연결</code>(이 때, <strong>사이클이 발생하지 않도록 주의</strong>)</li> <li>최소신장트리가 만들어지기 전까지 2~3 과정 반복 수행</li> </ol> <p>그래프 내 간선의 개수가 적은 <strong>희소 그래프</strong>의 경우 크루스칼 알고리즘에 적합하다</p> <p><img src="../../assets/images/algorithm/graph/KruskalAlg.gif" alt="" class="align-center" /></p> <h2 id="프림-알고리즘prims-algorithm">프림 알고리즘(Prim’s Algorithm)</h2> <p>정점 위주의 알고리즘</p> <ol> <li>임의의 <code class="language-plaintext highlighter-rouge">정점</code>을 선택</li> <li>정점에 <code class="language-plaintext highlighter-rouge">인접</code>한 간선 중 가중치가 최소인 간선으로 <code class="language-plaintext highlighter-rouge">연결</code>된 정점을 선택</li> <li>위 정점에서 다시 최소 간선으로 연결된 정점을 선택</li> <li>최소신장트리가 만들어지기 전까지 2-3 과정 반복 수행</li> </ol> <p>그래프 내 간선의 개수가 많은 <strong>밀집 그래프</strong>의 경우 프림 알고리즘이 적합하다</p> <p><img src="../../assets/images/algorithm/graph/PrimAlg.gif" alt="" class="align-center" /></p> <h1 id="그래프의-순회graph-traversal">그래프의 순회(Graph Traversal)</h1> <p>하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 탐색이라 한다</p> <h2 id="dfs깊이-우선-탐색--depth-first-search"><strong>DFS</strong>(깊이 우선 탐색 : Depth-First Search)</h2> <p>아직 방문하지 않은 <code class="language-plaintext highlighter-rouge">자식</code> 노드를 우선적으로 탐색</p> <ol> <li>정점 i를 방문한다.</li> <li>정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면 이 정점을 모두 <code class="language-plaintext highlighter-rouge">STACK</code>에 저장한다</li> <li>스택에서 정점을 삭제하여 새로운 i를 설정하고 다시 1단계부터 수행</li> <li>스택이 공백이 되면 연산을 종료</li> </ol> <p><img src="../../assets/images/algorithm/graph/DFS.gif" alt="" class="align-center" /></p> <ul> <li><strong>특징</strong> <ul> <li> <p>현 경로상의 노드만을 기억하면 되므로 저장 공간의 수요가 비교적 적지만, 한 경로가 무한히 깊을 경우 <strong>오버플로우</strong>가 발생할 수 있다.<br /> 이를 방지하기 위해, 깊이에 <code class="language-plaintext highlighter-rouge">제한</code>을 두고 구현이 필요하다</p> </li> <li> <p>목표에 <strong>도달하지 못할 가능성이 존재</strong>하며, 도달할지라도 해당 경로가 <strong>최단 경로라고 보장할 수 없다</strong>.</p> </li> </ul> </li> </ul> <h2 id="bfs너비-우선-탐색--breadth-first-search"><strong>BFS</strong>(너비 우선 탐색 : Breadth-First Search)</h2> <p><code class="language-plaintext highlighter-rouge">형제</code> 노드를 우선적으로 탐색하는 기법</p> <ol> <li>임의의 시작 노드를 정해 <code class="language-plaintext highlighter-rouge">QUEUE</code>에 넣는다</li> <li>Dequeue연산을 통해 큐에서 노드를 가져와 현재 노드로 정한다</li> <li>현재 노드의 인접 노드 목록을 순회하면서 방문하지 않은 노드가 있는지 확인한다</li> <li>방문하지 않은 노드가 있다면 그 노드를 큐에 넣고 방문한다.</li> <li>큐가 공백이 될 때까지 2~4과정을 반복 수행</li> </ol> <p><img src="../../assets/images/algorithm/graph/BFS.gif" alt="" class="align-center" /></p> <ul> <li><strong>특징</strong> <ul> <li>큐에 다음에 탐색할 정점들을 저장해야 하므로 <strong>저장공간이 많이 필요</strong></li> <li>단순 검색속도가 DFS보다 빠르다</li> <li>최단 경로를 보장함과 동시에 <strong>반드시 찾을 수 있다</strong></li> </ul> </li> </ul>

신장 트리(Spanning Tree)

그래프 내의 모든 정점을 포함하는 트리
최소 연결 부분 그래프.

N개의 정점을 가지는 그래프의 최소 간선의 수는 N-1개이며, N-1개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 이루어지고 이것이 바로 Spanning Tree라 할 수 있다.

하나의 그래프에는 많은 신장 트리가 존재할 수 있으며, 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야 하고 사이클을 포함해서는 안된다.

최소 신장트리(MST : Minimum Spanning Tree)

가능한 신장트리에서 간선의 가중치 합이 최소인 신장트리를 의미

최소 비용 신장 트리를 구하는 방법들은 모두 탐욕 알고리즘(Greedy Algorithm)으로 구현

** 탐욕 알고리즘 : 각 단계에서 최선의 선택이 최종 단계에서도 최선의 결과를 나타낼 것이라고 생각하는 알고리즘

크루스칼 알고리즘(Kruskal’s Algorithm)

간선 위주의 알고리즘.

1. 모든 간선들의 가중치를 오름차순으로 정렬
2. 가중치가 최소인 간선을 선택
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결(이 때, 사이클이 발생하지 않도록 주의)
4. 최소신장트리가 만들어지기 전까지 2~3 과정 반복 수행

그래프 내 간선의 개수가 적은 희소 그래프의 경우 크루스칼 알고리즘에 적합하다

프림 알고리즘(Prim’s Algorithm)

정점 위주의 알고리즘

1. 임의의 정점을 선택
2. 정점에 인접한 간선 중 가중치가 최소인 간선으로 연결된 정점을 선택
3. 위 정점에서 다시 최소 간선으로 연결된 정점을 선택
4. 최소신장트리가 만들어지기 전까지 2-3 과정 반복 수행

그래프 내 간선의 개수가 많은 밀집 그래프의 경우 프림 알고리즘이 적합하다

그래프의 순회(Graph Traversal)

하나의 정점에서 시작하여 그래프에 있는 모든 정점을 한번씩 방문하는 것을 그래프 순회 또는 탐색이라 한다

DFS(깊이 우선 탐색 : Depth-First Search)

아직 방문하지 않은 자식 노드를 우선적으로 탐색

1. 정점 i를 방문한다.
2. 정점 i에 인접한 정점 중에서 아직 방문하지 않은 정점이 있으면 이 정점을 모두 STACK에 저장한다
3. 스택에서 정점을 삭제하여 새로운 i를 설정하고 다시 1단계부터 수행
4. 스택이 공백이 되면 연산을 종료

• 특징

  • 현 경로상의 노드만을 기억하면 되므로 저장 공간의 수요가 비교적 적지만, 한 경로가 무한히 깊을 경우 오버플로우가 발생할 수 있다.
    이를 방지하기 위해, 깊이에 제한을 두고 구현이 필요하다

  • 목표에 도달하지 못할 가능성이 존재하며, 도달할지라도 해당 경로가 최단 경로라고 보장할 수 없다.

BFS(너비 우선 탐색 : Breadth-First Search)

형제 노드를 우선적으로 탐색하는 기법

1. 임의의 시작 노드를 정해 QUEUE에 넣는다
2. Dequeue연산을 통해 큐에서 노드를 가져와 현재 노드로 정한다
3. 현재 노드의 인접 노드 목록을 순회하면서 방문하지 않은 노드가 있는지 확인한다
4. 방문하지 않은 노드가 있다면 그 노드를 큐에 넣고 방문한다.
5. 큐가 공백이 될 때까지 2~4과정을 반복 수행

• 특징
  • 큐에 다음에 탐색할 정점들을 저장해야 하므로 저장공간이 많이 필요
  • 단순 검색속도가 DFS보다 빠르다
  • 최단 경로를 보장함과 동시에 반드시 찾을 수 있다