Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Can someone review this code, just have look if it's logically correct

or

If you may point me to a more simple and minimalist program

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * Created by aishwat on 17/8/16.
 */
public class PrimsMST {
    public class Node implements Comparable<Node> {
        int vertice, key;

        Node(int vertice, int key) {
            this.vertice = vertice;
            this.key = key;
        }

        @Override
        public int compareTo(Node o) {
            return this.key - o.key;
        }
    }

    public class AdjList {
        ArrayList<Node> nodes;
    }

    public class Graph {
        int V;
        AdjList[] adjLists;
    }


    public Graph createGraph(int v) {
        Graph graph = new Graph();
        graph.V = v;
        graph.adjLists = new AdjList[v];
        for (int i = 0; i < v; i++) {
            AdjList adjList = new AdjList();
            adjList.nodes = new ArrayList<Node>(); //initialize its node list too
            graph.adjLists[i] = adjList;
        }
        return graph;
    }

    public void addEdge(Graph graph, int src, int dest, int key) {
        Node srcNode = new Node(src, key);
        Node destNode = new Node(dest, key);
        graph.adjLists[src].nodes.add(destNode);
        graph.adjLists[dest].nodes.add(srcNode);
    }

    public void printGraph(Graph graph) {
        for (int i = 0; i < graph.V; i++) {
            System.out.print(i + " ->");
            for (Node node : graph.adjLists[i].nodes) {
                System.out.print(" " + node.vertice);
            }
            System.out.println();
        }
    }

    public void getPrimsMST(Graph graph) {
        Node keys[] = new Node[graph.V];
        int parent[] = new int[graph.V];
        boolean mstSet[] = new boolean[graph.V];

        for (int i = 0; i < graph.V; i++) {
            keys[i] = new Node(i, Integer.MAX_VALUE);
            parent[i] = -1;
            mstSet[i] = false;
        }
        keys[0].key = 0;
        Queue<Node> pQueue = new PriorityQueue<>();
        pQueue.addAll(Arrays.asList(keys));


        while (pQueue.size() > 1) {
            Node u = pQueue.remove();
            mstSet[u.vertice] = true;

            for (Node node : graph.adjLists[u.vertice].nodes) {

                if (mstSet[node.vertice] == false && node.key < keys[node.vertice].key) {
                    pQueue.remove(keys[node.vertice]); //remove that node from q

                    keys[node.vertice].key = node.key; //change key
                    parent[node.vertice] = u.vertice;

                    pQueue.add(keys[node.vertice]); //add back
                    //remove add can me made single function by using a visited flag 
                    //remove_add() in O(lg(n))
                 }

            }
        }
        print_mst(keys, parent, graph);

    }

    public void print_mst(Node[] keys, int[] parent, Graph graph) {
        for (int i = 1; i < graph.V; i++) {
            System.out.println(parent[keys[i].vertice] + "-" + keys[i].vertice + " " +keys[i].key);
        }
    }

    public static void main(String[] args) {
        int V = 9;
        PrimsMST MST = new PrimsMST();
        Graph graph = MST.createGraph(V);
        MST.addEdge(graph, 0, 1, 4);
        MST.addEdge(graph, 0, 7, 8);
        MST.addEdge(graph, 1, 2, 8);
        MST.addEdge(graph, 1, 7, 11);
        MST.addEdge(graph, 2, 3, 7);
        MST.addEdge(graph, 2, 8, 2);
        MST.addEdge(graph, 2, 5, 4);
        MST.addEdge(graph, 3, 4, 9);
        MST.addEdge(graph, 3, 5, 14);
        MST.addEdge(graph, 4, 5, 10);
        MST.addEdge(graph, 5, 6, 2);
        MST.addEdge(graph, 6, 7, 1);
        MST.addEdge(graph, 6, 8, 6);
        MST.addEdge(graph, 7, 8, 7);


        // print the adjacency list representation of the above graph
        MST.printGraph(graph);
        System.out.println();
        MST.getPrimsMST(graph);

    }
}

I know remove is O(n), ignore that part

Also is Dijkstra different from Prim's , apart from fact that it has specified origin ?

share|improve this question

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.