Topological sort: Difference between revisions
→{{header|Go}}: add DFS version
(→{{header|Go}}: Replace with better version. (Previous version was mine and was horrible.)) |
(→{{header|Go}}: add DFS version) |
||
Line 1,305:
=={{header|Go}}==
===Kahn===
<lang go>package main
Line 1,452 ⟶ 1,453:
<pre>
Cyclic: [dw01 dw04]
</pre>
===Depth First===
Topological sort only, this function can replace topSortKahn in above program. The
in-degree list is not needed.
<lang go>// General purpose topological sort, not specific to the application of
// library dependencies. Also adapted from Wikipedia pseudo code.
func topSortDFS(g graph) (order, cyclic []string) {
L := make([]string, len(g))
i := len(L)
temp := map[string]bool{}
perm := map[string]bool{}
var cycleFound bool
var cycleStart string
var visit func(string)
visit = func(n string) {
switch {
case temp[n]:
cycleFound = true
cycleStart = n
return
case perm[n]:
return
}
temp[n] = true
for _, m := range g[n] {
visit(m)
if cycleFound {
if cycleStart > "" {
cyclic = append(cyclic, n)
if n == cycleStart {
cycleStart = ""
}
}
return
}
}
delete(temp, n)
perm[n] = true
i--
L[i] = n
}
for n := range g {
if perm[n] {
continue
}
visit(n)
if cycleFound {
return nil, cyclic
}
}
return L, nil
}</lang>
{{out}}
(when used in program of Kahn example.)
<pre>
Order: [ieee gtech synopsys dware dw07 dw06 dw02 dw01 dw04 std_cell_lib dw05 std ramlib dw03 des_system_lib]
</pre>
And with the cycle added,
<pre>
Cyclic: [dw04 dw01]
</pre>
| |||