×

What is the easiest way to implement prim's algorithm in java?

 0 I tried to implement prim's algorithm in java but I found it difficult to implement. Can any one help me to implement prim's algorithm using built in data structure(Collections framework) asked 13 Dec '16, 08:53 1★arpit728 683●15●62 accept rate: 10%

 0 For starters you can have a look at the following links:- Prims code in java Java prims implementation you can have a look at both the links but, i think this would not work for extremely large data sets as both of the codes maintain a adjacency matrix for the graph, for large data sets you have to maintain either a 2-D pair or a vector of pairs answered 13 Dec '16, 11:56 99●3 accept rate: 25%
 0 Here's the code import java.util.*; public class PRIMS { static class EDGE{ int from, to; double weight; EDGE(int f, int t, double w){ from = f; to = t; weight = w; } } public static ArrayList prims(ArrayList> G){ if(G.isEmpty())throw new NullPointerException("The Graph is empty"); ArrayList mst = new ArrayList<>(); PriorityQueue pq = new PriorityQueue<>((Object o1, Object o2) -> { EDGE first = (EDGE)o1; EDGE second = (EDGE)o2; if(first.weightsecond.weight)return 1; else return 0; }); for(EDGE e:G.get(0)){ pq.add(e); } boolean[] marked = new boolean[G.size()]; marked[0] = true; while(!pq.isEmpty()){ EDGE e = pq.peek(); pq.poll(); if(marked[e.from] && marked[e.to])continue; marked[e.from] = true; for(EDGE edge:G.get(e.to)){ if(!marked[edge.to]){ pq.add(edge); } } marked[e.to] = true; mst.add(e); } return mst; } public static ArrayList> createGraph(EDGE[] edges){ ArrayList> G = new ArrayList<>(); int length = edges.length*2; for(int i=0;i()); } for(EDGE e:edges){ EDGE other = new EDGE(e.to, e.from, e.weight); G.get(e.from).add(e); G.get(e.to).add(other); System.out.println("Added edge ["+e.from+", "+e.to+" : "+e.weight+"] "+"["+e.to+", "+e.from+" : "+e.weight+"]"); } return G; } public static void main(String[] args){ EDGE[] edges = new EDGE[16]; edges[0] = new EDGE(0, 7, 0.16); edges[1] = new EDGE(2, 3, 0.17); edges[2] = new EDGE(1, 7, 0.19); edges[3] = new EDGE(0, 2, 0.26); edges[4] = new EDGE(5, 7, 0.28); edges[5] = new EDGE(1, 3, 0.29); edges[6] = new EDGE(1, 5, 0.32); edges[7] = new EDGE(2, 7, 0.34); edges[8] = new EDGE(4, 5, 0.35); edges[9] = new EDGE(1, 2, 0.36); edges[10] = new EDGE(4, 7, 0.37); edges[11] = new EDGE(0, 4, 0.38); edges[12] = new EDGE(6, 2, 0.40); edges[13] = new EDGE(3, 6, 0.52); edges[14] = new EDGE(6, 0, 0.58); edges[15] = new EDGE(6, 4, 0.93); ArrayList> graph = createGraph(edges); ArrayList mst = prims(graph); System.out.println("MST: "); for(EDGE e:mst){ System.out.println(e.from+" - "+e.to+" : "+e.weight); } }  } answered 13 Dec '16, 21:04 81●5 accept rate: 12%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,278
×1,197
×72
×35
×7

question asked: 13 Dec '16, 08:53

question was seen: 5,730 times

last updated: 13 Dec '16, 21:04