缘起

最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用golang练习之

图的搜索

  1. 图的搜索指的就是从图的某一顶点开始，
  2. 通过边到达不同的顶点，
  3. 最终找到目标顶点的过程。
  5. 根据搜索的顺序不同，
  6. 图的搜索算法可分为“广度优先搜索”和“深度优先搜索”这两种。
  8. 虽然广度优先搜索和深度优先搜索在搜索顺序上有很大的差异，
  9. 但是在操作步骤上却只有一点不同，
  10. 那就是选择哪一个候补顶点作为下一个顶点的基准不同。
  12. 广度优先搜索选择的是最早成为候补的顶点(FIFO)，
  13. 而深度优先搜索选择的则是最新成为候补的顶点(LIFO)。
  15. 摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一

目标

  • 通过替换候选节点的选择方式(LIFO, FIFO), 分别实现并验证深度优先搜索和广度优先搜索

设计

  • INode: 顶点接口
  • IGraphVisitor: 图的遍历器接口
  • tNode: 顶点的实现
  • iNodeQueue: 候选节点队列. 候选节点的选择方式不同, 决定了是深度优先还是广度优先.
  • tLIFOQueue: LIFO堆栈, 实现iNodeQueue接口
  • tFIFOQeuue: FIFO队列, 实现iNodeQueue接口
  • tGraphVisitor: 遍历器, 实现IGraphVisitor接口,
    • 从指定顶点出发, 访问所有可到达的顶点, 然后返回顶点数组
    • 使用哈希表记录已访问节点, 防止重复访问

单元测试

graph_visit_test.go

  1. package graph
  3. import (
  4.     "fmt"
  5.     "learning/gooop/graph"
  6.     "strings"
  7.     "testing"
  8. )
  10. func Test_GraphVisit(t *testing.T) {
  11.     fnAssertTrue := func(b bool, msg string) {
  12.         if !b {
  13.             t.Fatal(msg)
  14.         }
  15.     }
  17.     root := graph.NewNode("ROOT")
  18.     a := graph.NewNode("a")
  19.     b := graph.NewNode("b")
  20.     root.Append(a)
  21.     root.Append(b)
  23.     ac := graph.NewNode("ac")
  24.     ad := graph.NewNode("ad")
  25.     a.Append(ac)
  26.     a.Append(ad)
  28.     be := graph.NewNode("be")
  29.     bf := graph.NewNode("bf")
  30.     b.Append(be)
  31.     b.Append(bf)
  33.     acg := graph.NewNode("acg")
  34.     ach := graph.NewNode("ach")
  35.     ac.Append(acg)
  36.     ac.Append(ach)
  38.     bfi := graph.NewNode("bfi")
  39.     bfj := graph.NewNode("bfj")
  40.     bf.Append(bfi)
  41.     bf.Append(bfj)
  43.     fnVisitGraph := func(policy graph.VisitPolicy) string {
  44.         lines := make([]string, 0)
  45.         nodes := graph.GraphVisitor.Visit(root, policy)
  46.         for _,it := range nodes {
  47.             lines = append(lines, fmt.Sprintf("%s", it))
  48.         }
  49.         return strings.Join(lines, " ")
  50.     }
  52.     t.Log("testing dfs visitor")
  53.     dfs := fnVisitGraph(graph.DFSPolicy)
  54.     t.Log(dfs)
  55.     fnAssertTrue(dfs == "ROOT-[a,b] b-[be,bf] bf-[bfi,bfj] bfj-[] bfi-[] be-[] a-[ac,ad] ad-[] ac-[acg,ach] ach-[] acg-[]", "expecting dfs result")
  57.     t.Log("testing bfs visitor")
  58.     bfs := fnVisitGraph(graph.BFSPolicy)
  59.     t.Log(bfs)
  60.     fnAssertTrue(bfs == "ROOT-[a,b] a-[ac,ad] b-[be,bf] ac-[acg,ach] ad-[] be-[] bf-[bfi,bfj] acg-[] ach-[] bfi-[] bfj-[]", "expecting bfs result")
  61. }

测试输出

  1. $ go test -v graph_visit_test.go 
  2. === RUN   Test_GraphVisit
  3.     graph_visit_test.go:53: testing dfs visitor
  4.     graph_visit_test.go:55: ROOT-[a,b] b-[be,bf] bf-[bfi,bfj] bfj-[] bfi-[] be-[] a-[ac,ad] ad-[] ac-[acg,ach] ach-[] acg-[]
  5.     graph_visit_test.go:58: testing bfs visitor
  6.     graph_visit_test.go:60: ROOT-[a,b] a-[ac,ad] b-[be,bf] ac-[acg,ach] ad-[] be-[] bf-[bfi,bfj] acg-[] ach-[] bfi-[] bfj-[]
  7. --- PASS: Test_GraphVisit (0.00s)
  8. PASS
  9. ok      command-line-arguments  0.002s

INode.go

顶点接口

  1. package graph
  3. type INode interface {
  4.     ID() string
  5.     Append(child INode)
  6.     Children() []INode
  7. }

IGraphVisitor.go

图的遍历器接口

  1. package graph
  3. type IGraphVisitor interface {
  4.     Visit(root INode, policy VisitPolicy) []INode
  5. }
  7. type VisitPolicy int
  8. const DFSPolicy VisitPolicy = 1
  9. const BFSPolicy VisitPolicy = 2

tNode.go

顶点的实现

  1. package graph
  3. import (
  4.     "fmt"
  5.     "strings"
  6. )
  8. type tNode struct {
  9.     id string
  10.     children []INode
  11. }
  13. func NewNode(id string) INode {
  14.     return &tNode{
  15.         id: id,
  16.         children: make([]INode, 0),
  17.     }
  18. }
  21. func (me *tNode) ID() string {
  22.     return me.id
  23. }
  25. func (me *tNode) Append(child INode) {
  26.     me.children = append(me.children, child)
  27. }
  29. func (me *tNode) Children() []INode {
  30.     return me.children
  31. }
  33. func (me *tNode) String() string {
  34.     items := make([]string, len(me.children))
  35.     for i,it := range me.children {
  36.         items[i] = it.ID()
  37.     }
  38.     return fmt.Sprintf("%v-[%s]", me.id, strings.Join(items, ","))
  39. }

iNodeQueue.go

候选节点队列接口. 候选节点的选择方式不同, 决定了是深度优先还是广度优先.

  1. package graph
  3. type iNodeQueue interface {
  4.     Clear()
  5.     Empty() bool
  6.     Push(node INode)
  7.     Poll() (bool, INode)
  8. }

tLIFOQueue.go

LIFO堆栈, 实现INodeQueue接口

  1. package graph
  4. type tLIFOQueue struct {
  5.     nodes []INode
  6.     capacity int
  7.     size int
  8. }
  10. func newLIFOQueue() iNodeQueue {
  11.     it := &tLIFOQueue{}
  12.     it.Clear()
  13.     return it
  14. }
  16. func (me *tLIFOQueue) Clear() {
  17.     me.nodes = make([]INode, 0)
  18.     me.capacity = 0
  19.     me.size = 0
  20. }
  22. func (me *tLIFOQueue) Push(node INode) {
  23.     me.ensureSpace(1)
  24.     me.nodes[me.size] = node
  25.     me.size++
  26. }
  28. func (me *tLIFOQueue) ensureSpace(space int) {
  29.     for me.capacity < me.size + space {
  30.         me.nodes = append(me.nodes, nil)
  31.         me.capacity++
  32.     }
  33. }
  35. func (me *tLIFOQueue) Empty() bool {
  36.     return me.size <= 0
  37. }
  39. func (me *tLIFOQueue) Poll() (bool, INode) {
  40.     if me.Empty() {
  41.         return false, nil
  42.     }
  44.     me.size--
  45.     it := me.nodes[me.size]
  46.     me.nodes[me.size] = nil
  47.     return true, it
  48. }

tFIFOQeuue.go

FIFO队列, 实现INodeQueue接口

  1. package graph
  4. type tFIFOQueue struct {
  5.     nodes []INode
  6.     capacity int
  7.     rindex int
  8.     windex int
  9. }
  11. func newFIFOQueue() iNodeQueue {
  12.     it := &tFIFOQueue{}
  13.     it.Clear()
  14.     return it
  15. }
  17. func (me *tFIFOQueue) Clear() {
  18.     me.nodes = make([]INode, 0)
  19.     me.capacity = 0
  20.     me.rindex = -1
  21.     me.windex = -1
  22. }
  24. func (me *tFIFOQueue) size() int {
  25.     return me.windex - me.rindex
  26. }
  28. func (me *tFIFOQueue) Empty() bool {
  29.     return me.size() <= 0
  30. }
  32. func (me *tFIFOQueue) Push(node INode) {
  33.     me.ensureSpace(1)
  34.     me.windex++
  35.     me.nodes[me.windex] = node
  36. }
  38. func (me *tFIFOQueue) ensureSpace(size int) {
  39.     for me.capacity < me.windex + size + 1 {
  40.         me.nodes = append(me.nodes, nil)
  41.         me.capacity++
  42.     }
  43. }
  45. func (me *tFIFOQueue) Poll() (bool, INode) {
  46.     if me.Empty() {
  47.         return false, nil
  48.     }
  50.     me.rindex++
  51.     it := me.nodes[me.rindex]
  52.     me.nodes[me.rindex] = nil
  54.     if me.rindex > me.capacity / 2 {
  55.         size := me.size()
  56.         offset := me.rindex + 1
  57.         for i := 0;i < size;i++ {
  58.             me.nodes[i], me.nodes[i + offset] = me.nodes[i + offset], nil
  59.         }
  61.         me.rindex -= offset
  62.         me.windex -= offset
  63.     }
  65.     return true, it
  66. }

tGraphVisitor.go

遍历器, 实现IGraphVisitor接口

  • 从指定顶点出发, 访问所有可到达的顶点, 然后返回顶点数组
  • 使用哈希表记录已访问节点, 防止重复访问 ```go package graph

type tGraphVisitor struct { }

func newGraphVisitor() IGraphVisitor { return &tGraphVisitor{ } }

func (me *tGraphVisitor) createQueue(policy VisitPolicy) iNodeQueue { switch policy { case BFSPolicy: return newFIFOQueue()

  1. case DFSPolicy:
  2.     return newLIFOQueue()
  4. default:
  5.     panic("unsupported policy")
  6. }

}

func (me *tGraphVisitor) Visit(root INode, policy VisitPolicy) []INode { queue := me.createQueue(policy) queue.Push(root)

  1. visited := make(map[string]bool, 0)
  2. result := make([]INode, 0)
  3. for !queue.Empty() {
  4.     _,node := queue.Poll()
  5.     visited[node.ID()] = true
  6.     result = append(result, node)
  8.     children := node.Children()
  9.     if children != nil {
  10.         for _,it := range children {
  11.             ok,_ := visited[it.ID()]
  12.             if ok {
  13.                 continue
  14.             }
  15.             queue.Push(it)
  16.         }
  17.     }
  18. }
  20. return result

}

var GraphVisitor = newGraphVisitor() ```

(end)