FilesExpand file tree

master

/

depth_first_order.go

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

52 lines (46 loc) · 891 Bytes

master

/

depth_first_order.go

Copy path

Top

File metadata and controls

• Code
• Blame

52 lines (46 loc) · 891 Bytes

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

package algs4

// DepthFirstOrder ...

type DepthFirstOrder struct {

marked []bool

pre, post *Queue

reversePost *Stack

}

// NewDepthFirstOrder ...

func NewDepthFirstOrder(g *Digraph) *DepthFirstOrder {

d := &DepthFirstOrder{

marked: make([]bool, g.V()),

pre: NewQueue(),

post: NewQueue(),

reversePost: NewStack(),

}

for v := 0; v < g.V(); v++ {

if !d.marked[v] {

d.Dfs(g, v)

}

}

return d

}

// Dfs ...

func (d *DepthFirstOrder) Dfs(g *Digraph, v int) {

d.pre.Enqueue(v)

d.marked[v] = true

for _, w := range g.Adj(v) {

if !d.marked[w] {

d.Dfs(g, w)

}

}

d.post.Enqueue(v)

d.reversePost.Push(v)

}

// Pre ...

func (d *DepthFirstOrder) Pre() *Queue {

return d.pre

}

// Post ...

func (d *DepthFirstOrder) Post() *Queue {

return d.post

}

// ReversePost ...

func (d *DepthFirstOrder) ReversePost() *Stack {

return d.reversePost

}