그래프 검색 결과
3 개의 검색 결과가 있습니다.
알고리즘

Prim 알고리즘 자바로 구현 (백준 1197번)

2021.08.30 - [알고리즘] - Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해 Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해 Minimum Spanning Tree와 Prim 알고리즘에 대해 설명하기 전, 먼저 Spanning Tree의 정의부터 살펴보자. Spanning Tree란 그래프 중 모든 정점이 간선으로 연결되어 있고 간선 간의 싸이클이 없는 그래프를 의미 lemonlemon.tistory.com 저번 포스팅에서 프림 알고리즘에 대해 다루었다. 그래프로 설명하면 어렵지 않지만 이를 자바 코드로는 어떻게 구현할 수 있을까? 참고로 Minimum spanning tree를 코드로 구현하는 문제를 풀고 싶다면 백준 1197번을 참고하면..

2021. 8. 30. 15:21
알고리즘

Minimum Spanning Tree를 구현하는 Prim 알고리즘에 대해

Minimum Spanning Tree와 Prim 알고리즘에 대해 설명하기 전, 먼저 Spanning Tree의 정의부터 살펴보자. Spanning Tree란 그래프 중 모든 정점이 간선으로 연결되어 있고 간선 간의 싸이클이 없는 그래프를 의미한다. 여기 앞에 Minimum이 붙으면 각 간선간의 weight의 총합이 최소가 되게 연결이 되는 그래프를 뜻하는 것이다. 즉, 모든 vertex가 다 연결되도록 spanning tree를 만드는 방식이 여러 개가 있을 때 그 중 간선의 합들이 최소가 되도록 연결하는 것을 의미한다. 즉 위와 같은 그래프에서는 Minimum Spanning Tree는 아래와 같은 모양이다. 연결하는 다른 방법도 있지만 위와 같이 연결하면 총 weight가 최소가 된다. 그렇다면 위..

2021. 8. 30. 15:09
알고리즘

위상정렬 Topological Sort 개념 + 시간복잡도

Topological sort 위상정렬 알고리즘에 대해서 살펴보고 시간복잡도를 분석해보도록 하자. 위상정렬 알고리즘이란 순서가 있는 알고리즘인데 쉽게 말해서, 만약 i와 j 사이에 간선이 있다면 i가 j보다 정렬 순서에서 먼저 와야 한다는 뜻이다. 일상 생활에서도 위상정렬이 필요한 경우를 쉽게 생각해볼 수 있다. 예를 들어, 일상생활에서 다음과 같이 5개 행동을 한다고 생각해보자. [물 끓이기, 요리하기, 음식먹기, TV 켜기, TV 보기] 그럴 때 물을 먼저 끓여야 요리를 할 수 있고 그래야 음식을 먹을 수 있다. 하지만 음식을 먹으면서 동시에 TV를 켜는 것은 가능하기 때문에 요리와 TV 사이의 순서는 정해져 있는 것이 없다. 하지만 TV를 켠 다음에야 TV를 볼 수 있으므로 아래와 같이 그래프가 만..

2021. 5. 9. 21:32