Prim Alqoritmi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Cisco Samsung
Qrafik Görməmiş Minimum Spanning Ağac Prim AlqoritmiBaxılıb 38

Tapmaq üçün Primin alqoritmindən istifadə olunur Minimum Spanning Ağac (MST) bağlı və ya yönləndirilməmiş graph. Bir qrafın spanning ağacı eyni zamanda bir altqrafdır ağac və bütün zirvələri əhatə edir. Minimum Spanning Tree, minimum kənar çəki cəminə sahib olan ağacdır.

misal

Qrafik

Prim AlqoritmiPinPin

Minimum Spanning Ağac (MST)

Prim AlqoritmiPinPin

Primin alqoritmi üçün alqoritm

Primin alqoritmi, biri daxil edilmiş təpələri (MST-də), digəri isə daxil edilməmiş təpələri (MST-də) təmsil edən iki dəsti qoruyan acgöz bir alqoritmdir.
Hər addımda, 1 dəstinin zirvələrini 2 dəstinin zirvələri ilə birləşdirən və kənarın digər tərəfindəki zirvəni 1 (və ya MST) ilə əhatə edən minimum çəki kənarını tapır.
Bir sıra zirvələri başqa bir təpələr dəsti ilə birləşdirən kənarlar qrupu kimi tanınır kəsmək qraf nəzəriyyəsində, buna görə Primin alqoritmi kəsikdə minimum çəki kənarını tapır və MST-də bu kənardakı təpəni daxil edir və bütün zirvələr MST-ə daxil olana qədər bu əməliyyatı təkrarlayır.

  1. Cari təpənin daxil olub-olmadığını (MST-də) əks etdirən bir sıra daxil edilmiş MST yaradın.
  2. Cari təpədən kəsilmiş hissədə minimum çəki kənarını əks etdirən başqa bir minEdgeCut massivi yaradın.
  3. MinEdgeCut'u bütün təpələr üçün SONRASI və ilk təpə üçün 0 olaraq başlayın.
  4. MinEdgeCut dəyəri olan (MST-də) olmayan bir təpə seçin (u deyin) və MST-ə daxil edin.
  5. MinEdgeCut dəyərlərini seçilmiş təpə üçün daxil edilməyən (MST-də) bütün bitişik təpələr üçün yeniləyin.
  6. Dəyərləri yeniləmək üçün v hər bitişik vertex üçün, uv kənarının çəkisi v-nin cari minEdgeCut dəyərindən azdırsa, minEdgeCut dəyərini uv-nin çəkisi kimi yeniləyin.
  7. Bütün təpələr daxil edilməyənə qədər 4, 5 və 6-cı addımları təkrarlayın.

Primin alqoritminin izahı

Aşağıdakı şəkildə göstərilən qrafiki nəzərdən keçirin, MST-ni tapmaq üçün yuxarıdakı alqoritmi tətbiq edək.

Prim AlqoritmiPinPin

Başlanğıcda, MST-də heç bir təpə yoxdur
dahilMST [] = {yalan, yalan, yalan, yalan}
minEdgeCut [] = {0, INFINITE, INFINITE, INFINITE}

MST-ə daxil olmayan minEdgeCut dəyərinə sahib olan təpə seçilir, yəni vertex 0, onu MST-ə daxil edir və bitişik olan minEdgeCut dəyərini yeniləyir. Belə ki,
dahilMST [] = {doğru, yalan, yalan, yalan}
minEdgeCut [] = {0, 5, 8, INFINITE}

Pin

Vertex 1 bu dəfə MST-ə daxil olmadığı və minimum minEdgeCut dəyərinə sahib olduğu üçün seçilir, onu MST-ə daxil edin və bitişik hissəsini yeniləyin. Belə ki,
dahilMST [] = {doğru, doğru, yalan, yalan}
minEdgeCut [] = {0, 5, 8, 15}

Pin

Vertex 2 seçildi. MST-yə daxil edin və qonşunu yeniləyin. Belə ki,
dahilMST [] = {doğru, doğru, doğru, yalan}
minEdgeCut [] = {0, 5, 8, 15}

Pin

Vertex 3 seçildi. MST-yə daxil edin və qonşunu yeniləyin. Belə ki,
dahilMST [] = {doğru, doğru, doğru, doğru}
minEdgeCut [] = {0, 5, 8, 15}

Prim AlqoritmiPinPin

Bütün zirvələr MST-ə daxil edilmişdir, buna görə də dayanırıq.

Primun alqoritmi üçün JAVA kodu

import java.util.ArrayList;
import java.util.Comparator;
import java.util.PriorityQueue;

public class PrimsAlgorithm {
    private static void findPrintMST(ArrayList<Edge> graph[]) {
        int n = graph.length;
        // parent array stores the parent vertex of the current vertex in MST
        int parent[] = new int[n];
        int minEdgeCut[] = new int[n];
        boolean includedMST[] = new boolean[n];

        // Initialise all minEdgeCut values as INFINITE and all vertices as not included in MST
        for (int i = 0; i < n; i++) {
            minEdgeCut[i] = Integer.MAX_VALUE;
            includedMST[i] = false;
        }

        // Initialise minEdgeCut value of first vertex as 0
        minEdgeCut[0] = 0;
        parent[0] = -1;

        // Create a min heap to pick the smallest minEdgeCut value at every step
        // Min heap of vertex and corresponding minEdgeCut value
        PriorityQueue<Element> minHeap = new PriorityQueue<>(new Comparator<Element>() {
            @Override
            public int compare(Element o1, Element o2) {
                return Integer.compare(o1.minEdgeCutValue, o2.minEdgeCutValue);
            }
        });
        for (int i = 0; i < n; i++)
            minHeap.add(new Element(i, minEdgeCut[i]));

        // While all vertices are not included in MST
        while(!minHeap.isEmpty()) {
            // Select the vertex with minimum minEdgeCut value
            int u = minHeap.poll().vertex;

            // Update minEdgeCut value for all adjacent vertices
            for (int j = 0; j < graph[u].size(); j++) {
                Edge curr = graph[u].get(j);
                // If weight of edge u-v is less than the current minEdgeCut value of v
                // update the minEdgeCut value as weight of u-v
                if (minEdgeCut[curr.to] > curr.weight && !includedMST[curr.to]) {
                    minEdgeCut[curr.to] = curr.weight;
                    parent[curr.to] = u;
                }
            }
        }

        // Print MST
        for (int i = 1; i < n; i++) {
            System.out.println("Edge from " + parent[i] + " to " + i + " weight " + minEdgeCut[i]);
        }
    }

    public static void main(String[] args) {
        // Graph
        ArrayList<Edge> graph[] = new ArrayList[4];
        for (int i = 0; i < 4; i++)
            graph[i] = new ArrayList<>();

        // Make the graph in given example
        graph[0].add(new Edge(1, 5));
        graph[0].add(new Edge(2, 8));
        graph[1].add(new Edge(0, 5));
        graph[1].add(new Edge(2, 10));
        graph[1].add(new Edge(3, 15));
        graph[2].add(new Edge(0, 8));
        graph[2].add(new Edge(1, 10));
        graph[2].add(new Edge(3, 20));
        graph[3].add(new Edge(1, 15));
        graph[3].add(new Edge(2, 20));

        // Find MST using Prim's Algorithm and print it
        findPrintMST(graph);
    }

    // Class representing an edge in the graph
    static class Edge {
        int to;
        int weight;

        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }

    // Class representing pair of vertex and its minEdgeCut value
    // Used in minHeap in Prim's Algorithm for MST
    static class Element {
        int vertex;
        int minEdgeCutValue;

        public Element(int vertex, int minEdgeCutValue) {
            this.vertex = vertex;
            this.minEdgeCutValue = minEdgeCutValue;
        }
    }
}

Primin alqoritmi üçün C ++ kodu

#include <bits/stdc++.h>
using namespace std;

// Class representing pair of vertex and its minEdgeCut value
// Used in minHeap in Prim's Algorithm for MST
class Element {
    public:
    int vertex;
    int minEdgeCutValue;
    Element(int v, int value) {
        vertex = v;
        minEdgeCutValue = value;
    }
};

// Class representing an edge in the graph
class Edge {
    public:
    int to;
    int weight;
    Edge(int t, int w) {
        to = t;
        weight = w;
    }
};

// Comparator to sort Element according to minEdgeCutValue
struct ElementComp {
    bool operator ()(const Element& e1, const Element& e2) {
        return (e2.minEdgeCutValue < e1.minEdgeCutValue);
    }
};

void findPrintMST(vector<Edge> graph[], int n) {
    // parent array stores the parent vertex of the current vertex in MST
    int parent[n];
    int minEdgeCut[n];
    bool includedMST[n];
    
    // Initialise all minEdgeCut values as INFINITE and all vertices as not included in MST
    for (int i = 0; i < n; i++) {
        minEdgeCut[i] = INT_MAX;
        includedMST[i] = false;
    }
    
    // Initialise minEdgeCut value of first vertex as 0
    minEdgeCut[0] = 0;
    parent[0] = -1;
    
    // Create a min heap to pick the smallest minEdgeCut value at every step
    // Min heap of vertex and corresponding minEdgeCut value
    priority_queue<Element, vector<Element>, ElementComp> minHeap;
    for (int i = 0; i < n; i++) {
        Element ele(i, minEdgeCut[i]);
        minHeap.push(ele);
    }
    
    // While all vertices are not included in MST
    while (minHeap.size() != 0) {
        // Select the vertex with minimum minEdgeCut value
        int u = minHeap.top().vertex;
        minHeap.pop();
        
        // Update minEdgeCut value for all adjacent vertices
        for (int j = 0; j < graph[u].size(); j++) {
            Edge curr = graph[u][j];
            // If weight of edge u-v is less than the current minEdgeCut value of v
            // update the minEdgeCut value as weight of u-v
            if (minEdgeCut[curr.to] > curr.weight && includedMST[curr.to] == false) {
                minEdgeCut[curr.to] = curr.weight;
                parent[curr.to] = u;
            }
        }
    }
    
    // Print MST
    for (int i = 1; i < n; i++) {
        cout<<"Edge from "<<parent[i]<<" to "<<i<<" weight "<<minEdgeCut[i]<<endl;
    }
}

int main() {
    vector<Edge> graph[4];
    
    // Make the graph in given example
    Edge e1(1, 5);
    Edge e2(2, 8);
    Edge e3(0, 5);
    Edge e4(2, 10);
    Edge e5(3, 15);
    Edge e6(0, 8);
    Edge e7(1, 10);
    Edge e8(3, 20);
    Edge e9(1, 15);
    Edge e10(2, 20);
    
    graph[0].push_back(e1);
    graph[0].push_back(e2);
    graph[1].push_back(e3);
    graph[1].push_back(e4);
    graph[1].push_back(e5);
    graph[2].push_back(e6);
    graph[2].push_back(e7);
    graph[2].push_back(e8);
    graph[3].push_back(e9);
    graph[3].push_back(e10);
    
    // Find MST using Prim's Algorithm and print it
    findPrintMST(graph, 4);
    
    return 0;
}
Edge from 0 to 1 weight 5
Edge from 0 to 2 weight 8
Edge from 1 to 3 weight 15

Mürəkkəblik təhlili

Zaman Mürəkkəbliyi = O (E log (V))burada E -> Kənarların sayı və V -> Təpələrin sayı.

Kosmik Mürəkkəblik = O (E + V) çünki E kənarları və V təpələri olan bir bitişiklik siyahısı yaradırıq.

References

Translate »