dew's CSE Studying

11.1 최소 비용 신장 트리신장 트리신장 트리(spanning tree): 그래프 내의 모든 정점을 포함하는 트리 1.모든 정점들이 연결되어 있어야 하고2.사이클을 포함해서는 안된다=>그래프에 있는 n개의 정점을 정확히 (n-1)개의 간선으로 연결하게 된다 -깊이우선/너비우선 탐색 도중 사용된 간선들만 표시하면 만들 수 있다-그래프의 최소 연결 부분 그래프최소: 간선의 수가 가장 적다(최소 n-1개의 간선)-통신 네트워크 구축에 많이 사용-각 링크의 구축 비용이 같지 않기 때문에 가장 적은 링크만 사용한다고 해서 최소 비용이 얻어지는 것은 아니다  최소 비용 신장 트리최소 비용 신장 트리(MST: minimum spanning tree): 네트워크에 있는 모든 정점들을 가장 적은 수의 간선과 비용으로 ..