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
|
package graph_test
import (
"fmt"
"github.com/yourbasic/graph"
)
const (
White = iota
Gray
Black
)
// The package doesn't support vertex labeling. However,
// since vertices are always numbered 0..n-1, it's easy
// to add this type of data on the side. This implementation
// of depth-first search uses separate slices to keep track of
// vertex colors, predecessors and discovery times.
type DFSData struct {
Time int
Color []int
Prev []int
Discover []int
Finish []int
}
func DFS(g graph.Iterator) DFSData {
n := g.Order() // Order returns the number of vertices.
d := DFSData{
Time: 0,
Color: make([]int, n),
Prev: make([]int, n),
Discover: make([]int, n),
Finish: make([]int, n),
}
for v := 0; v < n; v++ {
d.Color[v] = White
d.Prev[v] = -1
}
for v := 0; v < n; v++ {
if d.Color[v] == White {
d.dfsVisit(g, v)
}
}
return d
}
func (d *DFSData) dfsVisit(g graph.Iterator, v int) {
d.Color[v] = Gray
d.Time++
d.Discover[v] = d.Time
// Visit calls a function for each neighbor w of v,
// with c equal to the cost of the edge (v, w).
// The iteration is aborted if the function returns true.
g.Visit(v, func(w int, c int64) (skip bool) {
if d.Color[w] == White {
d.Prev[w] = v
d.dfsVisit(g, w)
}
return
})
d.Color[v] = Black
d.Time++
d.Finish[v] = d.Time
}
// Show how to use this package by implementing a complete depth-first search.
func Example_dFS() {
// Build a small directed graph:
//
// 0 ---> 1 <--> 2 3
//
g := graph.New(4)
g.Add(0, 1)
g.AddBoth(1, 2)
fmt.Println(g)
fmt.Println(DFS(g))
// Output:
// 4 [(0 1) {1 2}]
// {8 [2 2 2 2] [-1 0 1 -1] [1 2 3 7] [6 5 4 8]}
}
|
