[자료구조] spanning tree (sub graph)

자료구조

by ~지우~ 2022. 7. 1. 12:29

728x90

spanning tree: 그래프에서 cycle이 제거된 sub graph

-Depth First Traversal을 이용해 spanning tree 만들기

먼저 DFS방식으로 그래프를 순회한다.

위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결시키면 spanning tree가 만들어진다.

-Breadth First Traversal을 이용해 spanning tree 만들기

먼저 BFS방식으로 그래프를 순회한다.

위의 그림에서 서로 연결된 노드들만 그래프에서 다시 연결시키면 spanning tree가 만들어진다.

728x90

[자료구조] minimum spanning tree - prim's algorithim, kruskal's algrithm (0)	2022.07.04
[자료구조] 백준 1927번: 최소 힙 (0)	2022.07.04
[자료구조] 그래프(graph) 기본 개념/용어 정리 (0)	2022.06.28
[자료구조] 이진탐색트리(binary search tree) - T-tree (0)	2022.04.11
[자료구조] 이진탐색트리(binary search tree) - 2-3 Tree (0)	2022.04.11