Minimum Spanning Tree

1. Greedy Algorithms

　　Aside from Dynamic Programming, Greedy Algorithm is another kind of optimization maneuver, in which every time we make a locally optimal choice and finally get the global optimum. According to CLRS, a problem exhibits Optimal Substructure if an optimal solution to the problem contains optimal solutions to the sub-problems. A good case in point may be Huffman Coding, which generates optimal prefix code in light of the frequencies of different symbols. Here is my solution to an SJTU ACM Online Judge problem concerning such coding strategy:

import java.util.*;

class Huffman {
    private class Node {
        public int freq, sum;
        
        public Node(int freq,int sum) {
            this.freq = freq;
            this.sum = sum;
        }
    }
    private int size, len;
    private Node[] arr;
    
    public Huffman() {
        size = 50000;
        arr = new Node[size];
    }
    public void doubleSpace() {
        Node[] tmp = arr;
        arr = new Node[size<<1];
        for (int i=0;i<size;i++) {
            arr[i] = tmp[i];
        }
        size <<= 1;
    }
    public void getLeaf(int f) {
        if (len==size) {
            doubleSpace();
        }
        arr[len++] = new Node(f,0);
    }
    public int freqSum() {
        // Return the weighted sum of prefix code length
        PriorityQueue<Node> q = new PriorityQueue<Node>(len,
                new Comparator<Node>() {
                    public int compare(Node a,Node b) {
                        if (a.freq<b.freq) {
                            return -1;
                        } else if (a.freq>b.freq) {
                            return 1;
                        } else {
                            return 0;
                        }
                    }
                }
        );
        for (int i=0;i<len;i++) {
            q.add(arr[i]);
        }
        while (q.size()>1) {
            Node a = q.poll(), b = q.poll();
            q.add(new Node(a.freq+b.freq,a.freq+b.freq+a.sum+b.sum));
        }
        return q.peek().sum;
    }
}

public class Main {
    public static void main(String[] args) {
        Huffman tree = new Huffman();
        Scanner in = new Scanner(System.in);
        int n=in.nextInt(),tmp;
        for (int i=0;i<n;i++) {
            tmp = in.nextInt();
            tree.getLeaf(tmp);
        }
        System.out.println(tree.freqSum());
        in.close();
    }
}

2. Prim's Algorithm

　　To find a Minimal Spanning Tree of a given weighted graph, Prim's Algorithm is a greedy strategy in which we always choose an optimal vertex and connect it to the spanning tree. The following code is my solution to the USACO training problem "agrinet":

import java.io.*;
import java.util.*;

public class agrinet {
    public static final int INF = 100001;
    public static Scanner input;
    public static PrintWriter output;
    public static int num;
    public static int [][] cost;
    
    public static int genMST() {
        // Prim's Algorithm based on Adjacency Matrix:
        int val=0, pos=0;
        boolean vis[] = new boolean [num];
        int dist[] = new int [num];
        vis[0] = true;
        for (int i=1;i<num;i++) {
            dist[i] = INF;
        }
        for (int i=1;i<num;i++) {
            for (int j=0;j<num;j++) {
                // update all the remaining vertices
                if (!vis[j] && dist[j]>cost[pos][j])
                    dist[j] = cost[pos][j];
            }
            dist[pos] = INF;
            for (int j=0;j<num;j++) {
                // search for an optimal vertex
                if (!vis[j] && dist[j]<dist[pos]) {
                    pos = j;
                }
            }
            vis[pos] = true;
            val += dist[pos];
        }
        return val;
    }
    public static void main(String[] args) throws IOException {
        input = new Scanner(new FileReader("agrinet.in"));
        num = input.nextInt();
        cost = new int[num][num];
        for (int i=0;i<num;i++) {
            for (int j=0;j<num;j++) {
                cost[i][j] = input.nextInt();
            }
        }
        input.close();
        output = new PrintWriter(new FileWriter("agrinet.out"));
        output.println(genMST());
        output.close();
    }
}

3. Kruskal's Algorithm

　　Kruskal's Algorithm is another greedy method to build a Minimal Spanning Tree, in which every time we add an optimal safe edge to an edge set. Here I provide my solution an SJTU ACM Online Judge  problem as an example:

import java.util.*;

class DisjointSet {
    private int[] root;    // root of each item
    private int size;         // number of items
    
    public DisjointSet(int size) {
        if (size<=0) {
            throw new RuntimeException("Illegal Initial Size");
        } else {
            this.size = size;
            root = new int[size];
            for (int i=0;i<size;i++) {
                root[i] = -1;
            }
        }
    }
    public void union(int i,int j) {
        // Merge the set of i and the set of j
        if (i<0||i>=size||j<0||j>=size) {
            throw new RuntimeException("IndexOutOfBounds on union");
        } else {
            i = find(i);
            j = find(j);
            if (i!=j) {    
                // BEWARE that i and j may be identical
                if (root[i]<root[j]) {
                    root[i] += root[j];
                    root[j] = i;
                } else {
                    root[j] += root[i];
                    root[i] = j;
                }
            }
        }
    }
    public int find(int idx)  {
        // Determine and return root[idx]
        if (idx<0||idx>=size) {
            throw new RuntimeException("IndexOutOfBounds on find");
        } else {
            int prev = root[idx];
            if (prev<0) {
                return idx;
            } else {
                root[idx] = find(prev);
                return root[idx];
            }
        }
    }
}

class AdjList {
    private class Vert {
        public Edge next;
    }
    private class Edge {
        public int end, weight;
        public Edge next;
        
        public Edge(int end,int weight,Edge next) {
            this.end = end;
            this.weight = weight;
            this.next = next;
        }
    }
    private class HeapItem {
        public int start, end, weight;
        
        public HeapItem(int start,int end,int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }
    }
    
    public static final int INF = 100001;
    private int num;
    private Vert [] vert;
    
    public AdjList(int num) {
        this.num = num;
        vert = new Vert[num];
        for (int i=0;i<num;i++) {
            vert[i] = new Vert();
        }
    }
    public void insert(int i,int j,int w) {
        if (i<j) {
            vert[i].next = new Edge(j,w,vert[i].next);
        } else {
            vert[j].next = new Edge(i,w,vert[j].next);
        }
    }
    public int genMST() {
        // Kruskal's Algorithm based on Adjacency List:
        DisjointSet set = new DisjointSet(num);
        PriorityQueue<HeapItem> q = new PriorityQueue<HeapItem>(INF,
                new Comparator<HeapItem>() {
                    public int compare(HeapItem a,HeapItem b) {
                        if (a.weight<b.weight) {
                            return -1;
                        } else if (a.weight>b.weight) {
                            return 1;
                        } else {
                            return 0;
                        }
                    }
                }
        );
        for (int i=0;i<num;i++) {
            Edge itr = vert[i].next;
            while (itr!=null) {
                q.add(new HeapItem(i,itr.end,itr.weight));
                itr = itr.next;
            }
        }
        int cnt=0, val=0;
        while (cnt<num-1) {
            HeapItem e = q.poll();
            if (set.find(e.start)!=set.find(e.end)) {
                set.union(e.start,e.end);
                val += e.weight;
                cnt++;
            }
        }
        return val;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int v = in.nextInt();
        int e = in.nextInt();
        AdjList g = new AdjList(v);
        for (int i=0;i<e;i++) {
            int j = in.nextInt()-1;
            int k = in.nextInt()-1;
            int w = in.nextInt();
            g.insert(j,k,w);
        }
        in.close();
        System.out.println(g.genMST());
    }
}

 

References:

    1. Cormen, T. H. et al. Introduction to Algorithms [M] .  北京：机械工业出版社, 2006-09