Java Reference
In-Depth Information
figure 14.30
A topological sort. The
conventions are the
same as those in
Figure 14.21.
1
0
1
1
V
0
V
1
V
0
V
1
3
2
0
0
2
2
V
2
V
3
V
4
V
2
V
3
V
4
2
2
3
2
1
2
V
5
V
6
V
5
V
6
0
0
0
0
V
0
V
1
V
0
V
1
1
0
0
0
2
1
V
2
V
3
V
4
V
2
V
3
V
4
2
2
2
2
3
4
V
5
V
6
V
5
V
6
0
0
0
0
V
0
V
1
V
0
V
1
0
0
0
0
0
0
V
3
V
4
V
4
V
2
V
2
V
3
1
0
1
1
5
6
V
5
V
6
V
5
V
6
0
0
0
0
V
0
V
1
V
0
V
1
0
0
0
0
0
0
V
2
V
3
V
4
V
2
V
3
V
4
0
0
0
0
7
8
V
5
V
6
V
5
V
6
Two important issues to consider are
correctness
and
efficiency
.
Clearly, any
ordering produced by the algorithm is a topological order. The question is whether
every acyclic graph has a topological order, and if so, whether our algorithm is
guaranteed to find one. The answer is yes to both questions.
If at any point there are unseen vertices but none of them have an indegree
of 0, we are guaranteed that a cycle exists. To illustrate we can pick any vertex
A
0
. Because
A
0
has an incoming edge, let
A
1
be the vertex connected to it.
And as
A
1
has an incoming edge, let
A
2
be the vertex connected to it. We
The algorithm pro-
duces the correct
answer and detects
cycles if the graph
is not acyclic.
Search WWH ::
Custom Search