-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathPrims.java
More file actions
158 lines (136 loc) · 4.66 KB
/
Prims.java
File metadata and controls
158 lines (136 loc) · 4.66 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
/* package whatever; // don't place package name! */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* Created by tecso on 17/8/16.
*/
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 String toString()
{
return "vertex = "+this.vertice+" "+"key = "+this.key;
}
}
public class AdjList {
ArrayList<Node> nodes;
}
public class Graph {
int V;
AdjList[] adjLists;
//for 3 vertices, something like
//[]->[][][]
//[]->[][]
//[]->[][][][]
}
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));
System.out.println("Size"+pQueue.size());
System.out.println(" Prioirty Queue "+pQueue.toString());
while (pQueue.size() > 1) {
Node u = pQueue.remove();
mstSet[u.vertice] = true;
for (Node node : graph.adjLists[u.vertice].nodes) {
int v = node.vertice;
if (mstSet[v] == false && node.key < keys[v].key) {
pQueue.remove(keys[v]); //remove that node from q
keys[v].key = node.key; //change key
parent[v] = u.vertice;
pQueue.add(keys[v]); //add back
System.out.println(" Prioirty Queue "+pQueue.toString());
//remove add can me made single function by using a visited flag
// instead of actually removing node just mark it as dirty and use polling later
//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++) {
int v = keys[i].vertice;
System.out.println(parent[v] + "-" + v + " " +keys[v].key);
}
}
public static void main(String[] args) {
//int V = 9;
int V =6;
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);
*/
Graph graph = MST.createGraph(V);
MST.addEdge(graph,0, 1, 3);
MST.addEdge(graph,1, 2, 1);
MST.addEdge(graph,2, 0, 1);
MST.addEdge(graph,0, 3, 1);
MST.addEdge(graph,1, 3, 3);
MST.addEdge(graph,3, 4, 6);
MST.addEdge(graph,4, 5, 2);
MST.addEdge(graph,2, 4, 5);
MST.addEdge(graph,2, 5, 4);
// print the adjacency list representation of the above graph
MST.printGraph(graph);
System.out.println();
MST.getPrimsMST(graph);
}
}