Крускальскі алгарытм


Узровень складанасці Жорсткі
Часта пытаюцца ў амазонка
Глыбіня Першы пошук Саюз знайсці

Што такое алгарытм Крускаля?

Алгарытм Крускаля выкарыстоўваецца для пошуку мінімальнага ахопліваючага дрэва (MST) звязанага і ненакіраванага графік.

Прыклад

Графік

Крускальскі алгарытм

Мінімальны ахоп дрэва (MST)

Крускальскі алгарытм

Алгарытм

Алгарытм Крускаля - прагны алгарытм каб знайсці мінімальны ахоп дрэва.

  1. Сартаваць краю ў парадку ўзрастання ў адпаведнасці з іх вагой.
  2. На кожным кроку выбірайце самы маленькі край (з мінімальным вагой). Калі гэты край утварае цыкл з MST, які ўтварыўся да гэтага часу, адкіньце край, інакш дадайце яго ў MST.
  3. Паўтарайце крок 2, пакуль у MST адсутнічаюць усе вяршыні.

Тлумачэнне

Разгледзім графік, паказаны ў прыведзеным вышэй прыкладзе,

Рэбры на прыведзеным графіку:
Краю = {{0 да 1, вага = 5}, {0 да 2, маса = 8}, {1 да 2, маса = 10}, {1 да 3, маса = 15}, {2 да 3, маса = 20}}

Пасля сартавання краю
Краю = {{0 да 1 мас. = 5}, {0 да 2, мас. = 8}, {1 да 2, мас. = 10}, {1 да 3, мас. = 15}, {2 да 3, мас. = 20 }}

  • {0 да 1, вага = 5}, уключыце ў MST
  • {0 да 2, вага = 8}, уключыце ў MST
    Крускальскі алгарытм
  • {1 да 2, wt = 10}, утварае цыкл, не ўключаць у MST
  • {1 да 3, вага = 15}, уключыце ў MST
    Крускальскі алгарытм

Усе вяршыні ўключаны ў MST, таму мы спынімся на гэтым.

Праграма JAVA для алгарытму Крускаля

public class KruskalAlgorithm {
    // Function to find the set of element i
    private static int find(Subset subsets[], int i) {
        // Path Compression
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);

        return subsets[i].parent;
    }

    // Function to perform union of two sets of x and y
    private static void Union(Subset subsets[], int x, int y) {
        int xRoot = find(subsets, x);
        int yRoot = find(subsets, y);

        // (Union by Rank)
        if (subsets[xRoot].rank < subsets[yRoot].rank) {
            subsets[xRoot].parent = yRoot;
        } else if (subsets[xRoot].rank > subsets[yRoot].rank) {
            subsets[yRoot].parent = xRoot;
        } else {
            // If rank are same, then make one as root and increment
            // its rank by one
            subsets[yRoot].parent = xRoot;
            subsets[xRoot].rank++;
        }
    }

    private static void findPrintMST(ArrayList<Edge> graph[], Edge edges[]) {
        // Sort the edges in ascending order of their weights
        Arrays.sort(edges, Edge.comp);

        // Stores the mst
        Edge mst[] = new Edge[graph.length - 1];
        for (int i = 0; i < graph.length - 1; i++) {
            mst[i] = new Edge(-1, -1, -1);
        }
        int e = 0;      // Number of edges included in mst
        
        // Create v subsets, v is the number of vertices
        Subset subsets[] = new Subset[graph.length];
        for (int i = 0; i < graph.length; i++) {
            subsets[i] = new Subset();
        }
        // Initialise parent of all as itself and rank as 0
        for (int i = 0; i < graph.length; i++) {
            subsets[i].parent = i;
            subsets[i].rank = 0;
        }

        // One by one traverse all the edges
        for (int i = 0; i < edges.length; i++) {
            // Find the set of vertices present on this edge
            int x = find(subsets, edges[i].from);
            int y = find(subsets, edges[i].to);

            // If the set is not same(that is, no cycle is formed)
            // Add this edge to mst
            if (x != y) {
                mst[e].from = edges[i].from;
                mst[e].to = edges[i].to;
                mst[e].weight = edges[i].weight;
                Union(subsets, x, y);
                e++;
            } else {
                // Discard the edge
            }

            // If all the vertices are included in MST, stop here
            if (e == graph.length - 1) {
                break;
            }
        }
        
        // Print the MST
        for (int i = 0; i < graph.length - 1; i++) {
            System.out.println("From " + mst[i].from + " to " + mst[i].to + " weight " + mst[i].weight);
        }
    }

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

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

        // Store all the edges of the graph
        edges[0] = new Edge(0, 1, 5);
        edges[1] = new Edge(0, 2, 8);
        edges[2] = new Edge(1, 2, 10);
        edges[3] = new Edge(1, 3, 15);
        edges[4] = new Edge(2, 3, 20);

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

    static class Edge {
        int from;
        int to;
        int weight;

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

        public static final Comparator<Edge> comp = new Comparator<Edge>() {
            @Override
            public int compare(Edge o1, Edge o2) {
                // Sort according to edge weights
                return Integer.compare(o1.weight, o2.weight);
            }
        };
    }

    // Subset class is used to detect cycle while adding an edge
    static class Subset {
        int parent;
        int rank;
    }
}

Праграма C ++ для алгарытму Крускаля

#include <iostream>
#include<algorithm>
#include <vector>
using namespace std;

// class representing an Edge of a graph
class Edge {
    public:
    int from;
    int to;
    int weight;
    
    Edge(int f, int t, int w) {
        from = f;
        to = t;
        weight = w;
    }
};

// Subset class is used to detect cycle while adding an edge
class Subset {
    public:
    int parent;
    int rank;
};

// Function to find the set of element i
int find(Subset subsets[], int i) {  
    // Path compression
    if (subsets[i].parent != i)  
        subsets[i].parent = find(subsets, subsets[i].parent);  
  
    return subsets[i].parent;  
}

// Function to perform union of two sets of x and y
void Union(Subset subsets[], int x, int y) {  
    int xroot = find(subsets, x);  
    int yroot = find(subsets, y);  
  
    // Union by Rank
    if (subsets[xroot].rank < subsets[yroot].rank) {
        subsets[xroot].parent = yroot;  
    } else if (subsets[xroot].rank > subsets[yroot].rank) {
        subsets[yroot].parent = xroot;  
    } else {  
        // If ranks are same, then make one as root and  
        // increment its rank by one  
        subsets[yroot].parent = xroot;  
        subsets[xroot].rank++;  
    }  
}

void findPrintMST(vector<Edge> graph[], vector<Edge> &edges, int v) {
    // Sort the edges in ascending order of their weights
    sort(edges.begin(), edges.end(), 
        [](const Edge& lhs, const Edge& rhs) {
        return lhs.weight < rhs.weight;
        });
        
    // Stores the mst
    vector<Edge> mst;
    int e = 0;      // Number of edges included in mst
    
    // Create v subsets, v is the number of vertices
    Subset *subsets = new Subset[(v * sizeof(Subset))];
    // Initialise parent of all as itself and rank as 0
    for (int i = 0; i < v; i++) {
        subsets[i].parent = i;
        subsets[i].rank = 0;
    }
    
    // One by one traverse all the edges
    for (int i = 0; i < edges.size(); i++) {
        // Find the set of vertices present on this edge
        int x = find(subsets, edges[i].from);
        int y = find(subsets, edges[i].to);
        
        // If the set is not same(that is, no cycle is formed)
        // Add this edge to mst
        if (x != y) {
            Edge curr(edges[i].from, edges[i].to, edges[i].weight);
            mst.push_back(curr);
            Union(subsets, x, y);
            e++;
        } else {
            // Discard the edge
        }
        
        // If all the vertices are included in MST, stop here
        if (e == v - 1) {
            break;
        }
    }
    
    // Print the mst
    for (int i = 0; i < mst.size(); i++) {
        cout<<"From "<<mst[i].from<<" to "<<mst[i].to<<" weight "<<mst[i].weight<<endl;
    }
}

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

выхад

From 0 to 1 weight 5
From 0 to 2 weight 8
From 1 to 3 weight 15

Складанасць часу

O (E * часопіс (E) + E * часопіс (V)) дзе E пазначае колькасць граняў графіка, а V пазначае колькасць вяршыняў графіка.

Спасылкі