Skip to content

Commit 0cddbaf

Browse files
bravoo84bravoo84
authored
Uploading reverse krushkal cycle elimination in java
1 parent 50e8c29 commit 0cddbaf

1 file changed

Lines changed: 167 additions & 0 deletions

File tree

‎ReverseKrushkal.java‎

Lines changed: 167 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,167 @@
1+
2+
/*--- reverse cycle elimination of kruskal's algorithm---*/
3+
4+
import java.io.*;
5+
import java.util.*;
6+
7+
class Graph
8+
{
9+
private int V; // No. of vertices
10+
private LinkedList<Integer> adj[]; //Adjacency Lists
11+
12+
void addEdge(int v,int w)
13+
{
14+
adj[v].add(w);
15+
adj[w].add(v);
16+
}
17+
void removeEdge(int v,int w){
18+
19+
for(int i=0;i<adj[v].size();i++){
20+
int t=adj[v].get(i);
21+
if(t==w){
22+
adj[v].remove(i);
23+
}
24+
}
25+
26+
for(int i=0;i<adj[w].size();i++){
27+
int t=adj[w].get(i);
28+
if(t==v){
29+
adj[w].remove(i);
30+
}
31+
}
32+
33+
}
34+
35+
boolean BFS(int s,int d)
36+
{
37+
boolean visited[] = new boolean[V];
38+
39+
// Create a queue for BFS
40+
LinkedList<Integer> queue = new LinkedList<Integer>();
41+
42+
// Mark the current node as visited and enqueue it
43+
visited[s]=true;
44+
queue.add(s);
45+
46+
while (queue.size() != 0)
47+
{
48+
49+
s = queue.poll();
50+
if(s==d) return true;//cycle exist
51+
Iterator<Integer> i = adj[s].listIterator();
52+
while (i.hasNext())
53+
{
54+
int n = i.next();
55+
if (!visited[n])
56+
{
57+
visited[n] = true;
58+
queue.add(n);
59+
}
60+
}
61+
}
62+
return false; //cycle doesnt exist
63+
}
64+
class Edge implements Comparable<Edge>{
65+
66+
int src,dest,weight;
67+
@Override
68+
public int compareTo(Edge compareEdge) {
69+
return this.weight-compareEdge.weight;
70+
}
71+
}
72+
int E;
73+
Edge edge[];
74+
Graph(int v,int e){
75+
V=v;
76+
E=e;
77+
edge=new Edge[E];
78+
for(int i=0;i<e;i++){
79+
edge[i]=new Edge();
80+
}
81+
adj = new LinkedList[v];
82+
for (int i=0; i<v; ++i)
83+
adj[i] = new LinkedList<Integer>();
84+
}
85+
86+
void ReverseKruskal(){
87+
88+
Edge result[]=new Edge[V];
89+
for(int i=0;i<V;i++){
90+
result[i]=new Edge();
91+
}
92+
93+
Arrays.sort(edge);
94+
95+
int i=0;
96+
int e=0;
97+
while(e<V-1){
98+
Edge next_edge=new Edge();
99+
next_edge=edge[E-i-1];
100+
i++;
101+
removeEdge(next_edge.src,next_edge.dest);
102+
103+
if(!BFS(next_edge.src,next_edge.dest)){
104+
result[e++]=next_edge;
105+
}//else eliminate
106+
}
107+
108+
System.out.println("Edge\t\tCorresponding edge weight");
109+
for(i=0;i<e;i++){
110+
System.out.println(result[i].src+"---"+result[i].dest+"\t\t"+result[i].weight);
111+
}
112+
113+
}
114+
}
115+
116+
public class ReverseKrushkal {
117+
public static void main(String[] args) {
118+
int V=6;
119+
int E=8;
120+
121+
122+
123+
Graph graph=new Graph(V,E);
124+
125+
graph.edge[0].src=0;
126+
graph.edge[0].dest=1;
127+
graph.edge[0].weight=4;
128+
graph.addEdge(0, 1);
129+
130+
graph.edge[1].src = 1;
131+
graph.edge[1].dest = 2;
132+
graph.edge[1].weight = 8;
133+
graph.addEdge(1, 2);
134+
135+
graph.edge[2].src = 1;
136+
graph.edge[2].dest = 4;
137+
graph.edge[2].weight = 11;
138+
graph.addEdge(1, 4);
139+
140+
graph.edge[3].src = 0;
141+
graph.edge[3].dest = 4;
142+
graph.edge[3].weight = 8;
143+
graph.addEdge(0, 4);
144+
145+
graph.edge[4].src = 5;
146+
graph.edge[4].dest = 2;
147+
graph.edge[4].weight = 2;
148+
graph.addEdge(5, 2);
149+
150+
graph.edge[5].src = 5;
151+
graph.edge[5].dest = 3;
152+
graph.edge[5].weight = 6;
153+
graph.addEdge(5, 3);
154+
155+
graph.edge[6].src = 4;
156+
graph.edge[6].dest = 5;
157+
graph.edge[6].weight = 7;
158+
graph.addEdge(4, 5);
159+
160+
graph.edge[7].src = 4;
161+
graph.edge[7].dest = 3;
162+
graph.edge[7].weight = 1;
163+
graph.addEdge(4, 3);
164+
165+
graph.ReverseKruskal();
166+
}
167+
}

0 commit comments

Comments
 (0)