[알고리즘] 최소 신장 트리 (feat.프림 알고리즘)

---

저번 크루스칼 알고리즘 포스팅에 이어서, 최소 신장 트리를 찾는 대표 알고리즘인 프림 알고리즘에 대해 알아보겠습니다.

* 크루스칼 알고리즘

https://geukggom.tistory.com/177

 

 

<목차>

1. 프림 알고리즘이란?

2. 프림 알고리즘 구현

---

1. 프림 알고리즘이란?

: 크루스칼 알고리즘과 마찬가지로 탐욕 알고리즘을 기반으로 하고 있습니다. 크루스칼 알고리즘과 차이점이 있다면, 크루스칼 알고리즘은 가중치가 가장 작은 간선부터 선택한다면, 프림 알고리즘은 특정 정점에서 시작해서 해당 정점에 연결된 가장 작은 가중치를 선택합니다.

 

---

2. 프림 알고리즘 구현

1) Edge 만들기 

public class Edge : IComparable
{
    public int weight; //가중치
    public string node1;
    public string node2;
    public Edge(int weight, string node1, string node2)
    {
        this.weight = weight;
        this.node1 = node1;
        this.node2 = node2;
    }

    public int CompareTo(object obj)
    {
        Edge edge = obj as Edge;
        return edge.weight;
    }

    public string myData()
    {
        return this.weight + ":" + this.node1 + "," + this.node2;
    }
}

 

2) 그래프 생성

예시 그래프 :

출처 :&nbsp; https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

이번에는 Minimum Heap을 이용해서 그래프를 생성해줍니다.

* MinHeap은 여기 포스팅에서 코드를 작성한 바 있어 링크 올립니다.

https://geukggom.tistory.com/175

 

MinHeap graph = new MinHeap();
graph.addHeap(new Edge(29, "A", "B"));
graph.addHeap(new Edge(10, "A", "F"));
graph.addHeap(new Edge(16, "B", "C"));
graph.addHeap(new Edge(15, "B", "G"));
graph.addHeap(new Edge(18, "D", "G"));
graph.addHeap(new Edge(12, "C", "D"));
graph.addHeap(new Edge(25, "G", "E"));
graph.addHeap(new Edge(22, "D", "E"));
graph.addHeap(new Edge(27, "E", "F"));
int num = graph.minHeap.Count;
while(graph.minHeap.Count > 1)
{
    Debug.Log(graph.heapOut().myData());
}

 

 

3) 프림 알고리즘

프림 알고리즘의 순서는 다음과 같습니다.

• 임의의 정점 선택
• 선택한 정점에 연결된 간선 리스트 for문 돌림
  • 이미 선택된 노드일 경우 스킵
  • 선택되지 않았던 노드일 경우 간선을 최소 신장 트리에 삽입 + 간선 리스트에서 제거
• 선택된 간선에 연결된 노드의 간선들도 간선리스트에 추가한 후, 위 과정 반복(간선 리스트가 텅 빌 때까지)

public List<Edge> primFunc(List<Edge> edgeList, string startNode)
{
    List<Edge> mst = new List<Edge>();
    List<Edge> currentEdgeList, candidateEdgeList, adjacentEdgeList = new List<Edge>();
    Edge currentEdge, popEdge, adjacentEdge;

    List<string> connectedNodeList = new List<string>(); //mst에 연결된 노드 리스트

    Hashtable edgesHash = new Hashtable();
    for (int i = 0; i < edgeList.Count; i++)
    {
        currentEdge = edgeList[i];
        if (!edgesHash.Contains(currentEdge.node1)) edgesHash.Add(currentEdge.node1, new List<Edge>());
        if (!edgesHash.Contains(currentEdge.node2)) edgesHash.Add(currentEdge.node2, new List<Edge>());
    } //Hashtable에 Key값만 넣어줌(아직 리스트에 아무것도 없음)

    for (int i = 0; i < edgeList.Count; i++)
    {
        currentEdge = edgeList[i];
        currentEdgeList = (List<Edge>)edgesHash[currentEdge.node1];
        currentEdgeList.Add(new Edge(currentEdge.weight, currentEdge.node1, currentEdge.node2));
        currentEdgeList = (List<Edge>)edgesHash[currentEdge.node2];
        currentEdgeList.Add(new Edge(currentEdge.weight, currentEdge.node2, currentEdge.node1));
    } //Hashtable에 Edge도 마저 넣어줌

    connectedNodeList.Add(startNode); //시작 노드 넣어줌

    if (edgesHash.Contains(startNode)) candidateEdgeList = (List<Edge>)edgesHash[startNode];
    else candidateEdgeList = new List<Edge>(); 
    MinHeap heap = new MinHeap();
    for (int i = 0; i < candidateEdgeList.Count; i++)
    {
        heap.addHeap(candidateEdgeList[i]);
    }//minHeap에 시작 노드에 있는 Edge들 넣어줌

    while (heap.minHeap.Count > 1)
    {
        popEdge = heap.heapOut(); //간선 중 제일 짧은거 가져옴

        //popEdge.node2 = 선택한 간선에 연결된 반대쪽 노드
        //popEdge.node2가 이미 연결된 노드일 경우에는 패스
        if (!connectedNodeList.Contains(popEdge.node2))
        {
            connectedNodeList.Add(popEdge.node2);
            mst.Add(new Edge(popEdge.weight, popEdge.node1, popEdge.node2)); //mst에 간선 추가함

            //adjacentEdgeList에 node2에 연결된 간선들 넣어줌
            if (edgesHash.Contains(popEdge.node2)) adjacentEdgeList = (List<Edge>)edgesHash[popEdge.node2];
            else adjacentEdgeList = new List<Edge>();

            for (int i = 0; i < adjacentEdgeList.Count; i++)
            {
                adjacentEdge = adjacentEdgeList[i];
                if (!connectedNodeList.Contains(adjacentEdge.node2)) heap.addHeap(adjacentEdge);
            } //minHeap에 node2에 연결된 간선이 중복이 아닐 경우 추가해줌
        }
    }

    return mst;
}

 

---

GitHub