목록Darta structure (1)

YYYEJI

[DS] 최소 신장 트리(Minimum Spanning Tree)란?

신장 트리(Spanning Tree) 란? 한 Graph의 모든 vertex를 연결하는 cycle이 없는 sub graph입니다. - 스패닝 트리는 (n-1)개의 edge를 가진다. - 스패닝 트리는 DFS, BFS 알고리즘을 이용해 찾을 수 있다. (움직인 edge를 연결하면 된다.) - Cycle이 있어서는 안된다. 아래와 같은 그래프가 존재할 때 DFS, BFS spanning tree를 만들어보면 ↓↓↓ DFS ↓↓↓ https://yyyeji.tistory.com/379 [DS] 깊이 우선 탐색(DFS)이란? 하나의 vertax로부터 모든 vertex를 한 번씩 방문하는 그래프 탐색이 있습니다. ↓↓↓ 그래프란? ↓↓↓ https://yyyeji.tistory.com/378 [DS] 그래프(Gr..
Data structure 2023. 1. 24. 18:26
이전 Prev 1 Next 다음