-
Notifications
You must be signed in to change notification settings - Fork 1
/
dfs.go
60 lines (47 loc) · 916 Bytes
/
dfs.go
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
package path
import (
"github.com/aybabtme/graph"
)
type tremauxDFS struct {
g graph.Graph
from int
marked []bool
edgeTo []int
}
// BuildDFS builds a depth first search PathFinder for graph g starting from
// source s
func BuildDFS(g graph.Graph, s int) PathFinder {
t := tremauxDFS{
g: g,
from: s,
marked: make([]bool, g.V()),
edgeTo: make([]int, g.V()),
}
var visit func(v int)
visit = func(v int) {
t.marked[v] = true
for _, adj := range g.Adj(v) {
if !t.marked[adj] {
t.edgeTo[adj] = v
visit(adj)
}
}
}
visit(t.from)
return t
}
func (t tremauxDFS) HasPathTo(to int) bool {
return t.marked[to]
}
func (t tremauxDFS) PathTo(to int) []int {
if !t.HasPathTo(to) {
return []int{}
}
var path []int
for next := to; next != t.from; next = t.edgeTo[next] {
path = append(path, next)
}
path = append(path, t.from)
reverse(path)
return path
}