强化语法，回顾算法。

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

涉及到的Go语言语法：

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

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

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

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

算法比较基础，代码如下：

图使用的无向图演示，并使用邻接表保存。

package mainimport ("container/list""fmt"
)//adjacency table, 无向图
type Graph struct { adj []*list.List // double linklist storage the graph edgev   int // storage node's value
}//init graphh according to capacity
func newGraph(v int) *Graph { graphh := &Graph{ }graphh.v = vgraphh.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] = trueprev := make([]int, g.v)for index := range prev{ prev[index] = -1}var queue []intqueue = append(queue,s)visited[s] = truefound := falsefor 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 即空接口通过断言转为intif ok { if !visited[k] { prev[k] = topif k == n{ found = truebreak}queue = append(queue,k)visited[k] = true}}}}if found { printPath(prev,s,n)} else { fmt.Printf("no path found from %d to %d
",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] = trueisFound := falseself.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] = trueif s == t { isFound = truereturn}linkedlist := self.adj[s]for e := linkedlist.Front(); e != nil; e = e.Next() { k := e.Value.(int) // turn the nil interface to intif !visited[k] { prev[k] = sself.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