Go 分布式学习利器（15） -- Go 实现 深搜和广搜

强化语法，回顾算法。

通过Go语言实现 深度优先搜索 和 广度优先搜索，来查找社交网络中的三度好友关系（三度指的是一个节点到 其相邻节点 到 其相邻节点的节点 ，图递增三层好友关系）。

涉及到的Go语言语法：

1. Go的封装特性
2. 空接口和 断言
3. 数组的切片特性
4. Go 实现的双向链表库 – container/list

实现基本的搜索算法：深搜和广搜

深度优先搜索 就是沿着一个方向一直走，如果发现最后的结果是失败的，回溯到上一步，继续尝试其他分支。

广度优先搜索 就是层次搜索，将从当前节点到下一节点所有的步骤都走一遍，并保存走过的节点；到第三步时从保存的节点中取一个再走一步，将这一步所有的可达节点也都保存下来。

package main

import (
  "container/list"
  "fmt"
)

//adjacency table, 无向图
type Graph struct {
  adj []*list.List // double linklist storage the graph edge
  v   int // storage node's value
}

//init graphh according to capacity
func newGraph(v int) *Graph {
  graphh := &Graph{}
  graphh.v = v
  graphh.adj = make([]*list.List, v)
  for i := range graphh.adj {
    graphh.adj[i] = list.New()
  }
  return graphh
}

//insert as add edge，使用邻接表构建无向图
func (self *Graph) addEdge(s int, t int) {
  self.adj[s].PushBack(t)
  self.adj[t].PushBack(s)
}

// Find the path by bfs
func (g *Graph)bfs(s int, n int) {
  if s == n {
    return
  }

  visited := make([]bool, g.v)
  visited[s] = true

  prev := make([]int, g.v)
  for index := range prev{
    prev[index] = -1
  }

  var queue []int
  queue = append(queue,s)
  visited[s] = true

  found := false
  for len(queue) > 0 && !found {
    top := queue[0]
    queue = queue[1:] // 去掉头队头元素
    graphlink := g.adj[top]
    for edge := graphlink.Front(); edge != nil; edge = edge.Next() {
      k,ok := edge.Value.(int) // turn the nil interface to int 即空接口通过断言转为int
      if ok {
        if !visited[k] {
          prev[k] = top
          if k == n{
            found = true
            break
          }
          queue = append(queue,k)
          visited[k] = true
        }
      }
    }
  }

  if found {
    printPath(prev,s,n)
  } else {
    fmt.Printf("no path found from %d to %d\n",s,n )
  }

}

//search by DFS
func (self *Graph) DFS(s int, t int) {

  prev := make([]int, self.v)
  for i := range prev {
    prev[i] = -1
  }

  visited := make([]bool, self.v)
  visited[s] = true

  isFound := false
  self.recurse(s, t, prev, visited, isFound)

  printPath(prev, s, t)
  fmt.Println()
}

//recurse find path
func (self *Graph) recurse(s int, t int, prev []int, visited []bool, isFound bool) {

  if isFound {
    return
  }

  visited[s] = true

  if s == t {
    isFound = true
    return
  }

  linkedlist := self.adj[s]
  for e := linkedlist.Front(); e != nil; e = e.Next() {
    k := e.Value.(int) // turn the nil interface to int
    if !visited[k] {
      prev[k] = s
      self.recurse(k, t, prev, visited, false)
    }
  }

}

// print path recurse , to keep the visit sequence
func printPath(path []int ,s int ,n int) {
  if path[n] != -1 && n != s {
    printPath(path ,s, path[n])
  }
  fmt.Printf("%d ", n)
}

func main() {
  graph := newGraph(8)
  graph.addEdge(0, 1)
  graph.addEdge(0, 3)
  graph.addEdge(1, 2)
  graph.addEdge(1, 4)
  graph.addEdge(2, 5)
  graph.addEdge(3, 4)
  graph.addEdge(4, 5)
  graph.addEdge(4, 6)
  graph.addEdge(5, 7)
  graph.addEdge(6, 7)

  fmt.Println("BFS find 0-7: ")
  graph.bfs(0, 7)
  fmt.Println("BFS find 1-3: ")
  graph.bfs(1, 3)
  fmt.Println("DFS find 0-7: ")
  graph.DFS(0, 7)
  fmt.Println("DFS find 1-3: ")
  graph.DFS(1, 3)
  fmt.Println()
}      

BFS find 0-7: 
0 1 2 5 7 BFS find 1-3: 
1 0 3 
DFS find 0-7: 
0 1 2 5 4 6 7 
DFS find 1-3: 
1 0 3