缘起
最近浏览<<我的第一本算法书>>(【日】石田保辉；宫崎修一)
本系列笔记拟采纳golang练习之
图的搜寻
图的搜寻指的就是从图的某一顶点开始，通过边达到不同的顶点，最终找到指标顶点的过程。依据搜寻的程序不同，图的搜索算法可分为“广度优先搜寻”和“深度优先搜寻”这两种。尽管广度优先搜寻和深度优先搜寻在搜寻程序上有很大的差别，然而在操作步骤上却只有一点不同，那就是抉择哪一个候补顶点作为下一个顶点的基准不同。广度优先搜寻抉择的是最早成为候补的顶点(FIFO)，而深度优先搜寻抉择的则是最新成为候补的顶点(LIFO)。摘自 <<我的第一本算法书>> 【日】石田保辉；宫崎修一指标
- 通过替换候选节点的抉择形式(LIFO, FIFO), 别离实现并验证深度优先搜寻和广度优先搜寻
设计
- INode: 顶点接口
- IGraphVisitor: 图的遍历器接口
- tNode: 顶点的实现
- iNodeQueue: 候选节点队列. 候选节点的抉择形式不同, 决定了是深度优先还是广度优先.
- tLIFOQueue: LIFO堆栈, 实现iNodeQueue接口
- tFIFOQeuue: FIFO队列, 实现iNodeQueue接口
tGraphVisitor: 遍历器, 实现IGraphVisitor接口,
- 从指定顶点登程, 拜访所有可达到的顶点, 而后返回顶点数组
- 应用哈希表记录已拜访节点, 避免反复拜访
单元测试
graph_visit_test.go
package graphimport ( "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)PASSok command-line-arguments 0.002sINode.go
顶点接口
package graphtype INode interface { ID() string Append(child INode) Children() []INode}IGraphVisitor.go
图的遍历器接口
package graphtype IGraphVisitor interface { Visit(root INode, policy VisitPolicy) []INode}type VisitPolicy intconst DFSPolicy VisitPolicy = 1const BFSPolicy VisitPolicy = 2tNode.go
顶点的实现
package graphimport ( "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 graphtype iNodeQueue interface { Clear() Empty() bool Push(node INode) Poll() (bool, INode)}tLIFOQueue.go
LIFO堆栈, 实现INodeQueue接口
package graphtype 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 graphtype 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 graphtype 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)