크루스칼 알고리즘 (2) 썸네일형 리스트형 [알고리즘] 신장 트리, Kruskal 알고리즘 Spanning Tree 그래프 내의 모든 정점을 포함하는 트리를 의미한다. 즉 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 신장트리는 코딩테스트에서 그리디 알고리즘 문제로 자주 출제되는 유형 중 하나라고 한다. 위 그림은 신장트리의 예시이며 모든 정점을 포함하면서 사이클이 존재하지 않는 구조를 띄고 있다. DFS, BFS를 이용하여 그래프에서 신장 트리를 찾을 수 있으며 여러모양의 신장트리가 존재할 수 있다. 따라서 신장 트리는 그래프에 있는 n개의 정점을 n-1개의 간전으로 연결하여야 한다. 신장트리는 일반적으로 통신 네트워크를 구축할때 사용되기도 한다. Kruskal 알고리즘 신장트리에서 간선들의 가중치 합이 최소인 트리를 말한다. Minimum Spanning Tree .. [알고리즘] 그래프 이론 그래프 이론 코딩테스트에서 그래프이론을 활용하는 문제들은 대부분 난이도가 좀 있는 편이라고 생각한다. 지금까지 공부한 내용 중에서 DFS, BFS, 최단경로 알고리즘 모두 그래프를 이용하는 개념들이다. 알고리즘 문제에서 서로 다른 객체가 연결되어있다라는 내용이 내포되어있으면 가장 먼저 그래프 알고리즘 적용 여부를 판단해보아야 한다. 그래프 그래프는 정점과 간선으로 이루어진 자료구조 형태이다. 트리 또한 그래프의 일종이지만 트리는 방향성이 존재하고, 수직적인 관계를 가지고 있지만 그래프는 수직개념, 루트노드 등과 같은 개념이 없다. 즉 그래프는 네트워크 모델에 대한 관계를 나타낼때 효율적으로 사용될 수 있다. 대표적으로 지하철 노선도를 생각할 수 있다. 정점 - vertice : 노드라고 불리며 데이터가 .. 이전 1 다음
