목록2024/04/28 (1)
개발하는 리프터 꽃게맨입니다.
[알고리즘 스터디] 컴퓨터 과학에서 말하는 그래프 - 下
1. 신장 트리신장 트리(Spanning tree)란 그래프내의 모든 정점을 포함하는 부분 그래프(혹은 트리)이다.신장 트리는 특수한 형태로 모든 정점들이 연결되어 있어야 하고 사이클을 포함하면 안된다.따라서 신장 트리는 그래프에 있는 n개의 정점을 정확히 (n-1) 개의 간선으로 연결하게 된다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 신장 트리의 경우 BFS, DFS 를 사용하면 도중에 사용된 간선을 모아 만들 수 있다. 신장 트리는 그래프의 최소 연결 부분 그래프가 된다.여기서 최소의 의미는 간선의 수가 가장 적다는 의미이다.n개의 정점을 가지는 그래프는 최소한 (n-1)개의 간선을 가져야 하며, (n-1)개의 간선으로 연결되어 있으면 필연적으로 트리 형태가 되고 이것은 바로 신장 ..
스터디 자료
2024. 4. 28. 15:55