devlog

그래프에서 사이클이 존재하는지 여부는 dfs 를 사용해서 직관적으로 찾을 수 있다. 일반적인 그래프의 코드를 살펴보도록 하자 static void dfs(int v) { visit[v] = true; for(int u : adj[v]) { if(visit[u]) continue; dfs(u); } } v 라는 정점을 기준으로 dfs 를 수행한다고 했을 때 dfs(v) 가 끝나기 전에 v 를 재방문하는 일이 생기면 사이클이 존재함을 알 수 있다. 아래의 코드는 dfs 를 이용한 사이클 존재 여부를 확인하는 코드이다. static boolean cycle = false; static boolean[] visit = new boolean[n+1]; static boolean[] finished = new bo..

※ https://rh-tn.tistory.com/ 와 동시에 업로드 됩니다. 목차 1. Prim 알고리즘의 개념 2. Prim 알고리즘의 구현 3. Kruskal 알고리즘과 Prim 알고리즘의 비교 이전 포스팅에서는 최소 신장 트리를 만들기 위한 알고리즘으로 Kruskal 알고리즘에 대하여 알아보았습니다. 이번 포스팅에서는 최소 신장 트리를 구현하는 또 다른 알고리즘인 Prim 알고리즘에 대해 알아보도록 하겠습니다. Prim 알고리즘은 Union-Find 와 같은 알고리즘을 몰라도 구현할 수 있습니다. 하지만 구현이 Kruskal 알고리즘에 비해 복잡합니다. 개념 Prim 알고리즘은 다음과 같은 방법으로 동작을 수행합니다. 임의의 정점을 선택하여 최소 신장 트리에 추가합니다. 최소 신장 트리에 포함된 ..

※ https://rh-tn.tistory.com/ 와 동시에 업로드 됩니다. 목차 1. 최소 신장 트리의 정의 2. Kruskal 알고리즘의 개념 3. Kruskal 알고리즘 구현 정의 최소 신장 트리 (Minimum Spanning Tree)에 대해 알아보기 전에 우선 신장 트리가 무엇인지 알아보겠습니다. 신장 트리(Spanning Tree)는 무방향 연결 그래프가 존재할 때, 그 그래프에서 모든 정점을 포함하도록 간선을 부분적으로 선택하여 만들 수 있는 부분 그래프 입니다. 어떤 그래프가 정점 V개와 E개의 간선을 가지고 있다고 가정하면 신장 트리의 정점과 간선의 개수는 각각 V와 V-1이 되겠습니다. 최소 신장 트리는 그 중에서도 가중치가 있는 그래프일 때를 고려합니다. 그래프의 간선마다 가중치가..