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