FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java/DataStructures/Graphs/Kruskal.java at master · primary-code-test/Java · GitHub
primary-code-test
Java
Repository navigation
Code
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java
/
DataStructures
/
Graphs
/
Kruskal.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
103 lines (92 loc) · 3.73 KB
Breadcrumbs
Java
/
DataStructures
/
Graphs
/
Kruskal.java
Copy path
File metadata and controls
103 lines (92 loc) · 3.73 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
// Problem -> Connect all the edges with the minimum cost.
// Possible Solution -> Kruskal Algorithm (KA), KA finds the minimum-spanning-tree, which means, the
// group of edges with the minimum sum of their weights that connect the whole graph.
// The graph needs to be connected, because if there are nodes impossible to reach, there are no
// edges that could connect every node in the graph.
// KA is a Greedy Algorithm, because edges are analysed based on their weights, that is why a
// Priority Queue is used, to take first those less weighted.
// This implementations below has some changes compared to conventional ones, but they are explained
// all along the code.
import
java
.
util
.
Comparator
;
import
java
.
util
.
HashSet
;
import
java
.
util
.
PriorityQueue
;
public
class
Kruskal
{
// Complexity: O(E log V) time, where E is the number of edges in the graph and V is the number of
// vertices
private
static
class
Edge
{
private
int
from
;
private
int
to
;
private
int
weight
;
public
Edge
(
int
from
,
int
to
,
int
weight
) {
this
.
from
=
from
;
this
.
to
=
to
;
this
.
weight
=
weight
;
}
}
private
static
void
addEdge
(
HashSet
<
Edge
>[]
graph
,
int
from
,
int
to
,
int
weight
) {
graph
[
from
].
add
(
new
Edge
(
from
,
to
,
weight
));
}
public
static
void
main
(
String
[]
args
) {
HashSet
<
Edge
>[]
graph
=
new
HashSet
[
7
];
for
(
int
i
=
0
;
i
<
graph
.
length
;
i
++) {
graph
[
i
] =
new
HashSet
<>();
}
addEdge
(
graph
,
0
,
1
,
2
);
addEdge
(
graph
,
0
,
2
,
3
);
addEdge
(
graph
,
0
,
3
,
3
);
addEdge
(
graph
,
1
,
2
,
4
);
addEdge
(
graph
,
2
,
3
,
5
);
addEdge
(
graph
,
1
,
4
,
3
);
addEdge
(
graph
,
2
,
4
,
1
);
addEdge
(
graph
,
3
,
5
,
7
);
addEdge
(
graph
,
4
,
5
,
8
);
addEdge
(
graph
,
5
,
6
,
9
);
System
.
out
.
println
(
"Initial Graph: "
);
for
(
int
i
=
0
;
i
<
graph
.
length
;
i
++) {
for
(
Edge
edge
:
graph
[
i
]) {
System
.
out
.
println
(
i
+
" <-- weight "
+
edge
.
weight
+
" --> "
+
edge
.
to
);
}
}
Kruskal
k
=
new
Kruskal
();
HashSet
<
Edge
>[]
solGraph
=
k
.
kruskal
(
graph
);
System
.
out
.
println
(
"
\n
Minimal Graph: "
);
for
(
int
i
=
0
;
i
<
solGraph
.
length
;
i
++) {
for
(
Edge
edge
:
solGraph
[
i
]) {
System
.
out
.
println
(
i
+
" <-- weight "
+
edge
.
weight
+
" --> "
+
edge
.
to
);
}
}
}
public
HashSet
<
Edge
>[]
kruskal
(
HashSet
<
Edge
>[]
graph
) {
int
nodes
=
graph
.
length
;
int
[]
captain
=
new
int
[
nodes
];
// captain of i, stores the set with all the connected nodes to i
HashSet
<
Integer
>[]
connectedGroups
=
new
HashSet
[
nodes
];
HashSet
<
Edge
>[]
minGraph
=
new
HashSet
[
nodes
];
PriorityQueue
<
Edge
>
edges
=
new
PriorityQueue
<>((
Comparator
.
comparingInt
(
edge
->
edge
.
weight
)));
for
(
int
i
=
0
;
i
<
nodes
;
i
++) {
minGraph
[
i
] =
new
HashSet
<>();
connectedGroups
[
i
] =
new
HashSet
<>();
connectedGroups
[
i
].
add
(
i
);
captain
[
i
] =
i
;
edges
.
addAll
(
graph
[
i
]);
}
int
connectedElements
=
0
;
// as soon as two sets merge all the elements, the algorithm must stop
while
(
connectedElements
!=
nodes
&& !
edges
.
isEmpty
()) {
Edge
edge
=
edges
.
poll
();
// This if avoids cycles
if
(!
connectedGroups
[
captain
[
edge
.
from
]].
contains
(
edge
.
to
)
&& !
connectedGroups
[
captain
[
edge
.
to
]].
contains
(
edge
.
from
)) {
// merge sets of the captains of each point connected by the edge
connectedGroups
[
captain
[
edge
.
from
]].
addAll
(
connectedGroups
[
captain
[
edge
.
to
]]);
// update captains of the elements merged
connectedGroups
[
captain
[
edge
.
from
]].
forEach
(
i
->
captain
[
i
] =
captain
[
edge
.
from
]);
// add Edge to minimal graph
addEdge
(
minGraph
,
edge
.
from
,
edge
.
to
,
edge
.
weight
);
// count how many elements have been merged
connectedElements
=
connectedGroups
[
captain
[
edge
.
from
]].
size
();
}
}
return
minGraph
;
}
}
Back
|
FazBrowse Home
|
New Git URL