乐趣区

关于算法:手撸golang-基本数据结构与算法-图的搜索-深度优先广度优先

jiezi

缘起

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

图的搜寻 

 图的搜寻指的就是从图的某一顶点开始，通过边达到不同的顶点，最终找到指标顶点的过程。依据搜寻的程序不同，图的搜索算法可分为“广度优先搜寻”和“深度优先搜寻”这两种。尽管广度优先搜寻和深度优先搜寻在搜寻程序上有很大的差别，然而在操作步骤上却只有一点不同，那就是抉择哪一个候补顶点作为下一个顶点的基准不同。广度优先搜寻抉择的是最早成为候补的顶点 (FIFO)，而深度优先搜寻抉择的则是最新成为候补的顶点 (LIFO)。摘自 << 我的第一本算法书 >>【日】石田保辉；宫崎修一

指标

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

设计

  • INode: 顶点接口
  • IGraphVisitor: 图的遍历器接口
  • tNode: 顶点的实现
  • iNodeQueue: 候选节点队列. 候选节点的抉择形式不同, 决定了是深度优先还是广度优先.
  • tLIFOQueue: LIFO 堆栈, 实现 iNodeQueue 接口
  • tFIFOQeuue: FIFO 队列, 实现 iNodeQueue 接口

  • tGraphVisitor: 遍历器, 实现 IGraphVisitor 接口,

    • 从指定顶点登程, 拜访所有可达到的顶点, 而后返回顶点数组
    • 应用哈希表记录已拜访节点, 避免反复拜访

单元测试

graph_visit_test.go

package graph

import (
    "fmt"
    "learning/gooop/graph"
    "strings"
    "testing"
)

func Test_GraphVisit(t *testing.T) {fnAssertTrue := func(b bool, msg string) {
        if !b {t.Fatal(msg)
        }
    }

    root := graph.NewNode("ROOT")
    a := graph.NewNode("a")
    b := graph.NewNode("b")
    root.Append(a)
    root.Append(b)

    ac := graph.NewNode("ac")
    ad := graph.NewNode("ad")
    a.Append(ac)
    a.Append(ad)

    be := graph.NewNode("be")
    bf := graph.NewNode("bf")
    b.Append(be)
    b.Append(bf)

    acg := graph.NewNode("acg")
    ach := graph.NewNode("ach")
    ac.Append(acg)
    ac.Append(ach)

    bfi := graph.NewNode("bfi")
    bfj := graph.NewNode("bfj")
    bf.Append(bfi)
    bf.Append(bfj)

    fnVisitGraph := func(policy graph.VisitPolicy) string {lines := make([]string, 0)
        nodes := graph.GraphVisitor.Visit(root, policy)
        for _,it := range nodes {lines = append(lines, fmt.Sprintf("%s", it))
        }
        return strings.Join(lines, " ")
    }

    t.Log("testing dfs visitor")
    dfs := fnVisitGraph(graph.DFSPolicy)
    t.Log(dfs)
    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")

    t.Log("testing bfs visitor")
    bfs := fnVisitGraph(graph.BFSPolicy)
    t.Log(bfs)
    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")
}

测试输入 

$ go test -v graph_visit_test.go 
=== RUN   Test_GraphVisit
    graph_visit_test.go:53: testing dfs visitor
    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-[]
    graph_visit_test.go:58: testing bfs visitor
    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-[]
--- PASS: Test_GraphVisit (0.00s)
PASS
ok      command-line-arguments  0.002s

INode.go

顶点接口 

package graph

type INode interface {ID() string
    Append(child INode)
    Children() []INode
}

IGraphVisitor.go

图的遍历器接口 

package graph

type IGraphVisitor interface {Visit(root INode, policy VisitPolicy) []INode}

type VisitPolicy int
const DFSPolicy VisitPolicy = 1
const BFSPolicy VisitPolicy = 2

tNode.go

顶点的实现 

package graph

import (
    "fmt"
    "strings"
)

type tNode struct {
    id string
    children []INode}

func NewNode(id string) INode {
    return &tNode{
        id: id,
        children: make([]INode, 0),
    }
}


func (me *tNode) ID() string {return me.id}

func (me *tNode) Append(child INode) {me.children = append(me.children, child)
}

func (me *tNode) Children() []INode {return me.children}

func (me *tNode) String() string {items := make([]string, len(me.children))
    for i,it := range me.children {items[i] = it.ID()}
    return fmt.Sprintf("%v-[%s]", me.id, strings.Join(items, ","))
}

iNodeQueue.go

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

package graph

type iNodeQueue interface {Clear()
    Empty() bool
    Push(node INode)
    Poll() (bool, INode)
}

tLIFOQueue.go

LIFO 堆栈, 实现 INodeQueue 接口 

package graph


type tLIFOQueue struct {nodes []INode
    capacity int
    size int
}

func newLIFOQueue() iNodeQueue {it := &tLIFOQueue{}
    it.Clear()
    return it
}

func (me *tLIFOQueue) Clear() {me.nodes = make([]INode, 0)
    me.capacity = 0
    me.size = 0
}

func (me *tLIFOQueue) Push(node INode) {me.ensureSpace(1)
    me.nodes[me.size] = node
    me.size++
}

func (me *tLIFOQueue) ensureSpace(space int) {
    for me.capacity < me.size + space {me.nodes = append(me.nodes, nil)
        me.capacity++
    }
}

func (me *tLIFOQueue) Empty() bool {return me.size <= 0}

func (me *tLIFOQueue) Poll() (bool, INode) {if me.Empty() {return false, nil}

    me.size--
    it := me.nodes[me.size]
    me.nodes[me.size] = nil
    return true, it
}

tFIFOQeuue.go

FIFO 队列, 实现 INodeQueue 接口 

package graph


type tFIFOQueue struct {nodes []INode
    capacity int
    rindex int
    windex int
}

func newFIFOQueue() iNodeQueue {it := &tFIFOQueue{}
    it.Clear()
    return it
}

func (me *tFIFOQueue) Clear() {me.nodes = make([]INode, 0)
    me.capacity = 0
    me.rindex = -1
    me.windex = -1
}

func (me *tFIFOQueue) size() int {return me.windex - me.rindex}

func (me *tFIFOQueue) Empty() bool {return me.size() <= 0
}

func (me *tFIFOQueue) Push(node INode) {me.ensureSpace(1)
    me.windex++
    me.nodes[me.windex] = node
}

func (me *tFIFOQueue) ensureSpace(size int) {
    for me.capacity < me.windex + size + 1 {me.nodes = append(me.nodes, nil)
        me.capacity++
    }
}

func (me *tFIFOQueue) Poll() (bool, INode) {if me.Empty() {return false, nil}

    me.rindex++
    it := me.nodes[me.rindex]
    me.nodes[me.rindex] = nil

    if me.rindex > me.capacity / 2 {size := me.size()
        offset := me.rindex + 1
        for i := 0;i < size;i++ {me.nodes[i], me.nodes[i + offset] = me.nodes[i + offset], nil
        }

        me.rindex -= offset
        me.windex -= offset
    }

    return true, it
}

tGraphVisitor.go

遍历器, 实现 IGraphVisitor 接口

  • 从指定顶点登程, 拜访所有可达到的顶点, 而后返回顶点数组
  • 应用哈希表记录已拜访节点, 避免反复拜访 
package graph

type tGraphVisitor struct {
}

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

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

    case DFSPolicy:
        return newLIFOQueue()

    default:
        panic("unsupported policy")
    }
}

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

    visited := make(map[string]bool, 0)
    result := make([]INode, 0)
    for !queue.Empty() {_,node := queue.Poll()
        visited[node.ID()] = true
        result = append(result, node)

        children := node.Children()
        if children != nil {
            for _,it := range children {ok,_ := visited[it.ID()]
                if ok {continue}
                queue.Push(it)
            }
        }
    }

    return result
}

var GraphVisitor = newGraphVisitor()

(end)

退出移动版