이 문제같은 경우는 최소신장트리를 구하는 알고리즘이다. 최소신장트리를 구하는 알고리즘은 크게 프림알고리즘과 크루스칼알고리즘 두가지가 있다. 여기서 조금더 구현하기가 수월한 프림알고리즘을 이용하여 최소신장트리를 구현할것이다. 1. 최소신장 트리란? 최소 신장트리란 주어진 그래프에서 모든 정점을 연결하며 그 비용이 최소인 간선만 연결된 트리를 말한다. 2.프림 알고리즘(그림으로 설명하는 것이 편할 것같아 그림으로 ㅅ 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687..

이전에 게시했던 최단 거리문제가 코드가 동일하다. 단지 출력하는 부분의 코드만 살짝 수정해주면된다. 즉, 최소비용문제 또한 다익스트라 알고리즘으로 풀수 있다. 백준-1916번 최소비용 구하기 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091package graph; import java.util.ArrayList;import java.util.Iterator;import java.util.PriorityQueue;import java.util.Sc..

백준-1753번 최단거리 시작정점으로부터 모든 정점까지의 최단거리를 구하는 문제이다. 이 문제는 BFS와 비슷한 다익스트라 알고리즘으로 풀 수 있는 문제이다. 다익스트라 알고리즘은 방향이있는 가중치 그래프에서 어떤 정점에서 다른 정점까지의 최단 거리를 구할 수 있는 알고리즘이다.(음수간선을 포함하는 그래프는 다익스트라 알고리즘으로 풀 수 없다.) 위의 그림과 같은 과정으로 다익스트라 알고리즘이 구동됩니다. ( 코드에서는 방문여부에 관한 check배열은 선언하지 않았음 굳이 없어도 돌아감) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656..

1. 위상정렬위상정렬의 조건위상정렬이 가능하려면 DAG 그래프여야 한다. DAG란 Directed Acyclic Graph의 약자로 방향성이 있고, 사이클이 없는 그래프를 의미한다. 진입차수를 이용한 위상정렬 1.모든 정점의 선행 필요조건 관계를 따라 그래프를 그린다.(방향 그래프 완성)2. 각 정점에 대해 indegree를 센다.(자신으로 들어오는 간선의 개수)3. indegree가 0인 일을 모두 찾아 큐에 넣는다4. 큐에서 정점 하나를 꺼낸다.(위상정렬의 결과 출력을 위해 이때 꺼내진 정점을 출력하면 된다.)5. 방금 꺼낸 정점에 연결된 모든 정점들의 indegree를 1씩 감소시킨다.6. indegree가 감소된 정점들 중 indegree가 0인 정점이 있으면 큐에 넣어준다.7. 큐가 빌 때까지 ..

그래프 DFS(깊이우선탐색) 와 BFS(너비우선탐색) 1. 시작전그래프를 구현하는 방법 중에는 크게 두 가지가 있습니다. 첫번째는 인접행렬을 이용하는 방법이고, 두번째는 인접리스트를 이용하는 방법입니다. 이 두가지 방법중 인접행렬을 이용한 DFS 와 BFS를 구현해보겠습니다. 2.DFS(깊이우선탐색) 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182package graph; import java.util.Stack; public class DFS { class Vertex{ pu..