算法-图的遍历广度优先 BFS 和深度优先 DFS

图的两种遍历方式

如题，图的广度优先和深度优先遍历。和二叉树的广度优先遍历类似都利用队列先进先出的特点，不同点在于，二叉树的BFS不需要记录节点是否遍历过，但图会有环，需要记录哪些节点是否遍历过。

考察点

图的数据结构
BFS利用队列先进先出且节点是否遍历过
DFS利用栈后进先出

代码

图如下，使用邻接点表示法

/**

   B -----D------F
  /|     /|
 / |    / |
A  |   /  |
 \ |  /   |
  \| /    |
   C------E

**/

package main

import (
  "container/list"
  "fmt"
)

func main() {

    // 邻接表示
  var a = map[string][]string{
    "A": []string{"B", "C"},
    "B": []string{"A", "C", "D",},
    "C": []string{"A", "B", "D", "E"},
    "D": []string{"B", "C", "E", "F"},
    "E": []string{"C", "D"},
    "F": []string{"D"},
  }

  BFS(a, "A")
  fmt.Println("========")
  DFS(a, "A")

  // DFS(a, "D")
}

// 广度优先 利用队列
func BFS(g map[string][]string, node string) {
  visited := map[string]bool{
    node: true,
  }
  queue := list.New()
  queue.PushBack(node)
  for queue.Len() > 0 {
    // 队列=>先进先出
    front := queue.Remove(queue.Front()).(string)
    fmt.Println(front)

    for _, tmp := range g[front] {
      if !visited[tmp] {
        queue.PushBack(tmp)
        // 放进队列，表示遍历过
        visited[tmp] = true
      }
    }
  }
}

// 深度优先 利用栈
// 和BFS写法上的唯一区别就是弹出去的是最后一个
func DFS(g map[string][]string, node string) {
  visited := map[string]bool{
    node: true,
  }
  stack := list.New()
  stack.PushBack(node)
  for stack.Len() > 0 {
    // 栈=>后进先出
    back := stack.Remove(stack.Back()).(string)
    fmt.Println(back)

    for _, tmp := range g[back] {
      if !visited[tmp] {
        stack.PushBack(tmp)
        // 放进队列，表示遍历过
        visited[tmp] = true
      }
    }
  }

}

算法