Prims 알고리즘

Prims 알고리즘

2022-06-02 last update

5 minutes reading Data Structures & Algorithms

최소 생성 트리:


방향이 없는 그림을 무방향도라고 한다.각 그림에는 한 노드에서 다른 노드로 가는 경로가 있어야 합니다.생성 트리도 무방향 연결도로서 그림의 모든 노드는 최소 모서리를 가지고 있다.만약 생성 나무가 그림의 모든 노드가 없다면, 우리는 그것이 생성 나무라고 말할 수 없다.우리가 최소 권중 테두리를 통해 그림을 연결할 때, 트리를 생성하는 총 권중은 그림의 원시 권중보다 작을 것이다.생성 트리도 순환하지 않습니다.모든 그림에는 여러 개의 생성 트리가 있지만, 그 중 하나만 유일하다.우리는 모든 노드를 포함하는 완전한 그림을 만들고 낮은 권한을 유지하기 위해 최소 생성 트리라고 부른다.
우리는 다음 두 가지 방법으로 생성 트리를 그릴 수 있다.
  • Kruskal 알고리즘
  • 플럼 알고리즘
  • 본고에서 우리는 Prim의 알고리즘을 토론할 것이다.Kruskal의 알고리즘은 다음 글에서 논의될 것입니다.

    Prim 알고리즘:


    Prim 알고리즘은 그림의 최소 생성 트리를 찾는 데 사용됩니다.prim 알고리즘은 모든 노드에서 시작하여 가장 작은 인접 노드를 추가합니다. 이 과정은 접근도에 있는 모든 노드까지 지속됩니다.그림의 최소 생성 트리를 만들 때, 우리는 어떤 동그라미도 만들지 않아야 한다. 왜냐하면 동그라미는 최소 생성 트리에 있어서는 안 되기 때문이다.

    Prim 알고리즘 단계:


    prim의 알고리즘은 욕심 방법으로 최소 생성 트리를 구한다.우리는 그림의 어떤 정점을 선택한 다음에 다음 권한이 비교적 작은 인접 정점을 선택한 다음에 전체 그림 노드를 연결하지 않을 때까지 이 과정을 계속해야 한다.
    1단계: 도면에서 소스 교점을 선택합니다.
    단계 2: 소스와 인접한 최소 가중치 모서리를 찾아 생성 트리에 연결합니다.
    3단계: 모든 노드가 최소 생성 트리에 추가되지 않을 때까지 2단계를 반복합니다.

    예:


    다음은 Prim 알고리즘을 사용하여 최소 생성 트리를 검색하는 예입니다.
    우리는 그림 G에서 임의의 무작위 노드를 선택하여 최소 생성 트리(MST)에 추가합니다.여기서 노드 0을 선택합니다.

    현재, 우리는 원본 노드 (0) 와 인접하지만 무게가 가장 작은 모서리를 선택한 다음, 이 최소 무게 노드를 최소 생성 트리에 추가합니다.

    이제 원본 노드 (0 또는 1)와 인접하지만 무게가 가장 작은 모서리를 선택한 다음 최소 무게 노드를 최소 생성 트리에 추가합니다.

    이제 소스 노드 (0, 1 또는 3)와 인접하지만 가중치가 가장 작은 모서리를 선택한 다음 최소 가중치 노드를 최소 생성 트리에 추가합니다.

    이제 소스 노드 (0, 1, 3 또는 4)와 인접하지만 가장 작은 경계를 선택한 다음 최소 경계를 최소 생성 트리에 추가합니다.

    이제 소스 노드 (0, 1, 3, 4 또는 6) 와 인접하지만 가중치가 가장 작은 모서리를 선택한 다음 최소 가중치 노드를 최소 생성 트리에 추가합니다.

    이제 소스 노드(0, 1, 3, 4, 6 또는 2)와 인접하지만 가장 작은 모서리를 선택한 다음 최소 생성 트리에 추가합니다.

    다음은 Dell의 최종 MST(최소 트리 생성)로, 총 비용은 6입니다.

    C++Prim의 MST(최소 트리 생성) 프로그램:


    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    
    #include
    
    #include
    
    #include
    
    #include
    
    #include
    
    typedef std :: pair SII;
    
    typedef std :: vector SSII;
    
    int PrimsMST (int sourceNode, std :: vector & graph){
    
    // This queue will store details of each node
    
    // along with their weight value.
    
    std :: priority_queue, std :: greater> k;
    
    
    
    k.push(std :: make_pair(0, sourceNode));
    
    bool nodesAdded[graph.size()];
    
    memset(nodesAdded, false, sizeof(bool)*graph.size());
    
    int mst_tree_cost = 0;
    
    while (!k.empty()) {
    
    // We are selecting here the node which has minimum cost
    
    SII itemNode;
    
    itemNode = k.top();
    
    k.pop();
    
    int Node = itemNode.second;
    
    int Cost = itemNode.first;
    
    // Here we are checking if any node has not been added to the MST,
    
    // then adding that node.
    
    if (!nodesAdded[Node]) {
    
    mst_tree_cost += Cost;
    
    nodesAdded[Node] = true;
    
    // Iterate over the negibour nodes which were recently taken
    
    // out of the priority queue.
    
    // and added to the MST which is not yet added
    
    for (auto & pair_node_cost : graph[Node]) {
    
    int adjency_node = pair_node_cost.second;
    
    if (nodesAdded[adjency_node] == false) {
    
    k.push(pair_node_cost);
    
    }
    
    }
    
    }
    
    }
    
    return mst_tree_cost;
    
    }
    
    int main(){
    
    // The details of the graph with cost and adjency node.
    
    SSII fromNode_0_in_graph_1  = { {1,1}, {2,2}, {1,3},
    
    {1,4}, {2,5}, {1,6} };
    
    SSII fromNode_1_in_graph_1   = { {1,0}, {2,2}, {2,6} };
    
    SSII fromNode_2_in_graph_1   = { {2,0}, {2,1}, {1,3} };
    
    SSII fromNode_3_in_graph_1 = { {1,0}, {1,2}, {2,4} };
    
    SSII fromNode_4_in_graph_1  = { {1,0}, {2,3}, {2,5} };
    
    SSII fromNode_5_in_graph_1  = { {2,0}, {2,4}, {1,6} };
    
    SSII fromNode_6_in_graph_1   = { {1,0}, {2,2}, {1,5} };
    
    int num_of_nodes = 7; // Total Nodes (0 to 6)
    
    std :: vector primsgraph;
    
    primsgraph.resize(num_of_nodes);
    
    primsgraph[0] = fromNode_0_in_graph_1;
    
    primsgraph[1] = fromNode_1_in_graph_1;
    
    primsgraph[2] = fromNode_2_in_graph_1;
    
    primsgraph[3] = fromNode_3_in_graph_1;
    
    primsgraph[4] = fromNode_4_in_graph_1;
    
    primsgraph[5] = fromNode_5_in_graph_1;
    
    primsgraph[6] = fromNode_6_in_graph_1;
    
    // As we already know, we have to choose the source vertex,
    
    // so we start from the vertex 0 node.
    
    std :: cout << "Total cost of minimum spanning tree after Prim's algorithm : "
    
    "" << PrimsMST(0, primsgraph) << std :: endl;
    
    
    return 0;
    
    }

    출력:


    1
    2
    3
    
    Total cost of minimum spanning tree after Prim's algorithm : 6
    
    Process finished with exit code 0

    Prim의 MST 알고리즘 시간 복잡도:


    1. MST에 추가되지 않은 특정 우선 순위 대기열 노드를 처리하고 선택하는 데 걸리는 총 시간은 logV입니다.그러나 각 정점에 적용되기 때문에 총 시간 복잡도는 V(logV)이다.
    2. 그림은 방향이 없고 전체 변은 2E이다.우선 순위 대기열로 노드를 전송해야 하기 때문에 총 시간 로그 (V) 가 필요합니다.그러나, 우리는 모두 2E의 테두리가 있기 때문에, 우리의 총 밀기 작업은 2E (log (V) 가 될 것이다.
    3. 1과 2를 조작한 후의 총 복잡도는 O(E+V)log(V)이다.

    결론:


    우리는 Prim의 최소 생성 트리를 연구했는데, 이것은 대부분의 사람들이 그림에서 MST 그림을 찾을 때 가장 선호하는 것이다.Prim 알고리즘은 쉽게 파악되고 실제 응용에서 실현된다.Prim의 알고리즘은 실제 응용에서 매우 유용하다. 예를 들어 철도 궤도를 도시 전체에 연결하는 것이다.그래서 이것은 단지 하나의 예일 뿐이지만, 그것의 응용은 매우 크기 때문에 우리는 반드시 이 알고리즘을 이해해야 한다.