최소신장트리 (Minimum Spanning Tree) 신장트리 : 모든 정점들은 포함하고 간선은 (정점수-1) 개만 포함하는 트리, 사이클 없음 신장 트리 중에서 간선 가중치의 합이 최소인 신장 트리 ★Kruskal : Union-Find(Disjoint Set) 사용 O(|E|log|V|) Prim : 우선순위큐 사용 O(|E|log|V|) 간선을 기준으로 LinkedList에 담아 정렬 후 Union-Find Union Find by Rank 트리의 높이가 높을 수록 Find Set 수행시간 증가 Union 시 두 집합의 Root 중 Rank 값이 작은 Root를 큰 Root로 변경 Rank 값이 같을 경우에만 랭크 값 증가 public static void unionSet(int a, int b)..
시작점에서 가까운 정점부터 순서대로 방문 Queue O(|V|+|E|) 최단 경로 문제 해결 가중치가 없는 그래프 //V : 정점 집합, E : 간선 집합, Q : 큐 //visit[v] : 방분정보 저장 //Adj[v] : 정점 v의 인점 정접들 집합 //D[] : 시작점부터 각 정점까지 거리 //P[] : 최단 경로 트리 저장 bfs(s) { for (v : V) { D[v] = Max; P[v] = null; } D[s] = 0; P[s] = s; visit[s] = true; Q.offer(s); while(!Q.isEmpty()) { v = Q.poll(); for (인접 정점 u : Adj[v]) { if (visit[u] == false) { D[u] = D[v] + 1; P[u] = v; ..
인접한 간선 모두 방문 더 이상 갈 곳이 없으면 Back Tracking 재귀호출, Stack 그래프의 전체 구조를 파악 O(|V|²) 두 정점이 서로 연결되어 있는가 연결된 부분집합의 개수 세기 위상정렬 사이클 존재여부 //V : 정점 집합, E : 간선 집합 //visit[v] : 방문정보 저장 //Adj[v] : 정점 v의 인접 정점 집합 dfs(v) { visit[v] = true;//방문 처리 for (인접 정점 u : Adj[v]) { if (visit[u] == false)//인접 정점이 방문하지 않았다면 탐색 dfs(u); } }