FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
java/algorithms/graphs/TopologicalSort.java at master · AllAlgorithms/java · GitHub
Uh oh!
There was an error while loading.
Please reload this page
.
This repository was archived by the owner on Sep 7, 2025. It is now read-only.
AllAlgorithms
/
java
Public archive
Notifications
You must be signed in to change notification settings
Fork
83
Star
116
Code
Issues
3
Pull requests
6
Actions
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Security and quality
Insights
Expand file tree
Breadcrumbs
java
/
algorithms
/
graphs
/
TopologicalSort.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
80 lines (72 loc) · 2.85 KB
Breadcrumbs
java
/
algorithms
/
graphs
/
TopologicalSort.java
Copy path
File metadata and controls
80 lines (72 loc) · 2.85 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
import
java
.
util
.
InputMismatchException
;
import
java
.
util
.
Scanner
;
import
java
.
util
.
Stack
;
public
class
TopologicalSort
{
private
Stack
<
Integer
>
stack
;
public
TopologicalSort
() {
stack
=
new
Stack
<
Integer
>();
}
public
int
[]
topological
(
int
adjacency_matrix
[][],
int
source
)
throws
NullPointerException
{
int
number_of_nodes
=
adjacency_matrix
[
source
].
length
-
1
;
int
[]
topological_sort
=
new
int
[
number_of_nodes
+
1
];
int
pos
=
1
;
int
j
;
int
visited
[] =
new
int
[
number_of_nodes
+
1
];
int
element
=
source
;
int
i
=
source
;
visited
[
source
] =
1
;
stack
.
push
(
source
);
while
(!
stack
.
isEmpty
()) {
element
=
stack
.
peek
();
while
(
i
<=
number_of_nodes
) {
if
(
adjacency_matrix
[
element
][
i
] ==
1
&&
visited
[
i
] ==
1
) {
if
(
stack
.
contains
(
i
)) {
System
.
out
.
println
(
"TOPOLOGICAL SORT NOT POSSIBLE"
);
return
null
;
}
}
if
(
adjacency_matrix
[
element
][
i
] ==
1
&&
visited
[
i
] ==
0
) {
stack
.
push
(
i
);
visited
[
i
] =
1
;
element
=
i
;
i
=
1
;
continue
;
}
i
++;
}
j
=
stack
.
pop
();
topological_sort
[
pos
++] =
j
;
i
= ++
j
;
}
return
topological_sort
;
}
public
static
void
main
(
String
...
arg
) {
int
number_no_nodes
,
source
;
Scanner
scanner
=
null
;
int
topological_sort
[] =
null
;
try
{
System
.
out
.
println
(
"Enter the number of nodes in the graph"
);
scanner
=
new
Scanner
(
System
.
in
);
number_no_nodes
=
scanner
.
nextInt
();
int
adjacency_matrix
[][] =
new
int
[
number_no_nodes
+
1
][
number_no_nodes
+
1
];
System
.
out
.
println
(
"Enter the adjacency matrix"
);
for
(
int
i
=
1
;
i
<=
number_no_nodes
;
i
++)
for
(
int
j
=
1
;
j
<=
number_no_nodes
;
j
++)
adjacency_matrix
[
i
][
j
] =
scanner
.
nextInt
();
System
.
out
.
println
(
"Enter the source for the graph"
);
source
=
scanner
.
nextInt
();
System
.
out
.
println
(
"The Topological sort for the graph is given by "
);
TopologicalSort
toposort
=
new
TopologicalSort
();
topological_sort
=
toposort
.
topological
(
adjacency_matrix
,
source
);
System
.
out
.
println
();
for
(
int
i
=
topological_sort
.
length
-
1
;
i
>
0
;
i
--) {
if
(
topological_sort
[
i
] !=
0
)
System
.
out
.
print
(
topological_sort
[
i
] +
"
\t
"
);
}
}
catch
(
InputMismatchException
inputMismatch
) {
System
.
out
.
println
(
"Wrong Input format"
);
}
catch
(
NullPointerException
nullPointer
) {
}
scanner
.
close
();
}
}
Back
|
FazBrowse Home
|
New Git URL