앞서 봤던 크루스칼알고리즘은 모든 엣지들을 작은것 부터 오름차순으로 정렬한다(기준은 엣지의 가중치) 그리고 최소가중치를 지닌 엣지부터 탐색을 시작한다. 반면에 프림은 시작버텍스를 선택해야 한다. 그리고 연결된 집합, 연결되지 않은 집합 개념이 필요하다. 시작버텍스를 연결된 집합에 넣는다. 그리고 연결된 집합에 포함된 버텍스(지금은 1개)와 인접한 버텍스들 중에 엣지의 가중치가 작은 버텍스에 연결한다. 연결된 버텍스는 연결집합에 포함시킨다. 이렇게 반복이다.
크루스칼과 프림 둘다 탐욕알고리즘을 기반으로 한다(문제를 여러 단계에 걸쳐서 해결하는 방법이다. 현재 단계에서 최선의 선택을 한뒤 다음 단계에서도 최선의 선택을 하는 방법.)
그래프로 프림 알고리즘을 이해해보자 A를 시작 버텍스로 선택하였다
A를 연결된 집합에 포함시킨다. 연결된집합 A에서 최소 가중치를 가진 엣지를 탐색하고 7,8,10엣지중에서 7엣지 선택하고 B버텍스를 연결집합에 추가한다. 이제 A와 B가 연결집합에 포함되었다 이제 A와 B 버텍스들에 인접한 엣지중 최소 가중치를 찾는다
7,8,9,10 엣지중에 7은 이미 A,B가 연결집합에 포함되 있으므로 제외한다. 8엣지가 선택되고 C버텍스를 연결된 집합에 포함시킨다. 이제 A,B,C가 연결집합에 포함되었다
A,B,C 버텍스에 인접한 엣지를 찾는다. 7,8,9,9,10엣지가 있다
7,8은 제외한다(이미 A,B,C버텍스는 연결집합에 이미있으므로) 9,9 엣지 둘중 아무거나 선택하고 D버텍스 연결및 연결집합에 포함시킨다. 아래와 같이 두가지 경우로 나뉠것이다.
A,B,C,D가 연결집합에 포함되었다. 9,10번 간선들이 남지만 더 이상 연결집합에 추가시킬 버텍스가 없으므로 종료한다
이론적으로 프림알고리즘이 더 잘 이해가 된다
이전에 회사생활 할때는 버텍스(노드)를 중심으로 알고리즘을 짜다보니 엣지를 중심으로 구현하는게 생각보다 잘 안된다
이론 듣고 이해하고 구현하는데 3시간이나 걸렸다
첫번째 구현은 3중 for문이 들어가고 말았다.. 일단 구현해보고 정답을 보고 싶어서 어쨋든 돌아가게 만들었다.
함수 파라미터로 들어오는 그래프의 이미지
public class MyPrim {
MyPrim() {}
ArrayList<Edge> execute(String start, ArrayList<Edge> edges)
{
ArrayList<Edge> mst = new ArrayList<>();
PriorityQueue<Edge> queue = new PriorityQueue<>();
ArrayList<String> linkedvertices = new ArrayList<>();
linkedvertices.add(start);
for(Edge edge : edges )
{
if(edge.firstV.equals(start))
{
queue.add(edge);
}
}
while(queue.isEmpty() == false)
{
Edge edge = queue.poll();
linkedvertices.add(edge.secondV);
mst.add(edge);
queue.clear();
for(String vertex : linkedvertices)
{
for(Edge ele : edges)
{
if(ele.firstV.equals(vertex) && (false == linkedvertices.contains(ele.secondV)))
{
queue.add(ele);
}
}
}
}
return mst;
}
}package Prim;
import Kruskal.Edge;
import java.util.ArrayList;
import java.util.Arrays;
public class MyPrimTest {
public static void main(String[] args) {
ArrayList<Prim.Edge> edges = new ArrayList<>();
edges.add(new Prim.Edge(7, "A", "B"));
edges.add(new Prim.Edge(5, "A", "D"));
edges.add(new Prim.Edge(7, "B", "A"));
edges.add(new Prim.Edge(8, "B", "C"));
edges.add(new Prim.Edge(9, "B", "D"));
edges.add(new Prim.Edge(7, "B", "E"));
edges.add(new Prim.Edge(8, "C", "B"));
edges.add(new Prim.Edge(5, "C", "E"));
edges.add(new Prim.Edge(5, "D", "A"));
edges.add(new Prim.Edge(9, "D", "B"));
edges.add(new Prim.Edge(7, "D", "E"));
edges.add(new Prim.Edge(6, "D", "F"));
edges.add(new Prim.Edge(7, "E", "B"));
edges.add(new Prim.Edge(5, "E", "C"));
edges.add(new Prim.Edge(7, "E", "D"));
edges.add(new Prim.Edge(8, "E", "F"));
edges.add(new Prim.Edge(9, "E", "G"));
edges.add(new Prim.Edge(6, "F", "D"));
edges.add(new Prim.Edge(8, "F", "E"));
edges.add(new Prim.Edge(11, "F", "G"));
edges.add(new Prim.Edge(9, "G", "E"));
edges.add(new Prim.Edge(11, "G", "F"));
MyPrim priminst = new MyPrim();
ArrayList<Prim.Edge> result = priminst.execute("A", edges);
System.out.println(result);
}
}
개선된 프림 알고리즘을 구현해보자
정점을 기준으로 PriorityQueue를 적용해야함
정점과 가중치
public class MyPrimSecond {
public ArrayList<Path> improvedPrimFunc(HashMap<String, HashMap<String, Integer>> graph, String startNode)
{
ArrayList<Path> mst = new ArrayList<>();//minimumSpanningTree
PriorityQueue<Edge> pq = new PriorityQueue<>();
HashMap<String, Edge> mapEdgeObj = new HashMap<>();
HashMap<String, String> mapPath = new HashMap<>();
HashMap<String, Integer> mapAdjEdge = new HashMap<>();
Edge newEdge;
for(String key : graph.keySet())
{
if(key == startNode)
{
newEdge = new Edge(key, 0);
mapPath.put(key, key);
}
else
{
newEdge = new Edge(key, Integer.MAX_VALUE);
mapPath.put(key, null);
}
mapEdgeObj.put(key, newEdge);
pq.add(newEdge);
}
Edge curEdge = null;
Edge adjEdge;
while(pq.isEmpty() == false)
{
curEdge = pq.poll();
mapEdgeObj.remove(curEdge.vertex);
mst.add(new Path(mapPath.get(curEdge.vertex), curEdge.vertex, curEdge.weight));
mapAdjEdge = graph.get(curEdge.vertex);
for(String key : mapAdjEdge.keySet())
{
if(mapEdgeObj.containsKey(key))
{
adjEdge = mapEdgeObj.get(key);
if(mapAdjEdge.get(key) < adjEdge.weight)
{
adjEdge.weight = mapAdjEdge.get(key);
mapPath.put(key, curEdge.vertex);
pq.remove(adjEdge);
pq.add(adjEdge);
}
}
}
}
return mst;
}
}public class MyPrimSecondTest {
public static void main(String[] args) {
HashMap<String, HashMap<String, Integer>> mygraph = new HashMap<String, HashMap<String, Integer>>();
HashMap<String, Integer> edges;
edges = new HashMap<String, Integer>();
edges.put("B", 7);
edges.put("D", 5);
mygraph.put("A", edges);
edges = new HashMap<String, Integer>();
edges.put("A", 7);
edges.put("D", 9);
edges.put("C", 8);
edges.put("E", 7);
mygraph.put("B", edges);
edges = new HashMap<String, Integer>();
edges.put("B", 8);
edges.put("E", 5);
mygraph.put("C", edges);
edges = new HashMap<String, Integer>();
edges.put("A", 5);
edges.put("B", 9);
edges.put("E", 7);
edges.put("F", 6);
mygraph.put("D", edges);
edges = new HashMap<String, Integer>();
edges.put("B", 7);
edges.put("C", 5);
edges.put("D", 7);
edges.put("F", 8);
edges.put("G", 9);
mygraph.put("E", edges);
edges = new HashMap<String, Integer>();
edges.put("D", 6);
edges.put("E", 8);
edges.put("G", 11);
mygraph.put("F", edges);
edges = new HashMap<String, Integer>();
edges.put("E", 9);
edges.put("F", 11);
mygraph.put("G", edges);
MyPrimSecond mps = new MyPrimSecond();
ArrayList<Path> mst = mps.improvedPrimFunc(mygraph, "A");
System.out.println(mst);
}
}