缘起
最近阅读<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采用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.002sINode.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 = 2tNode.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)
有疑问加站长微信联系（非本文作者）
