小櫻的身體狀況越來越差，想必是Golang牌一張比一張還要難已經超出小五學童的腦力了。

但是這時天上又出現可怕的雲朵，一定是 DFS 和 BFS 搞得鬼。螢幕前的魔法使們可以幫助小櫻一起度過難關嗎？

使用更有彈性的 Graph

為了方便接下來的課程，我們來稍微改造一下昨天的 graph 包。

本篇文章接續 Day25 的課程，如果還沒看過的魔法使們請回去重看，不然無法收服

package graph
import (
    "container/list"
    "fmt"
)

type Graph struct{
    // 這次的 list 改用 map 來存，其中以 Vertex 來做索引
    // 突破只能用 int 來當 key 的限制
    adj_list map[*Vertex](*list.List)
}

type Vertex struct{
    Val interface{}    // Val 改為任意型態
}

// 創件 graph 時不在需要告訴有幾個節點
// 新增節點由 NewVertex 來添加
func NewGraph() *Graph{
    g := new(Graph)
    g.adj_list = make(map[*Vertex](*list.List))
    return g
}

// 新增節點的步驟改成綁定 Graph
// 利用 map 的特性來當成 adjacency list 最左側的陣列，可以更方便地處理新節點
func (g *Graph) NewVertex(number int) *Vertex{
    v := new(Vertex)
    v.Val = number
    g.adj_list[v] = list.New()
    return v
}

func (g *Graph) AddEdge(start, end *Vertex){
    g.adj_list[start].PushBack(end)
    g.adj_list[end].PushBack(start)
}

func (g *Graph) EasyTraversal(){
    // k's type is *Vertex
    // v's type is *list.List
    for k, v := range g.adj_list{
        fmt.Printf("[%v] -> ", k.Val)
        for current := v.Front(); current != nil; current = current.Next(){
            fmt.Printf("%v -> ", current.Value.(*Vertex).Val)
        }
        fmt.Println("nil")
    }
}

深度優先搜尋 DFS (Depth First Search)

如同名稱所言，深度優先搜尋會盡可能從起始點往深處搜尋，直到找不到新的鄰點才會回到前一次的搜尋做走訪

在範例中，我們以 0 為開始尋找的點，如果同時有多條可以選的話，預設選最小的 (其實只要隨機隨就可以了，但是為了講解方便，所以統一選最小的)

0 最先被印出來，跟 0 相鄰的有 1, 2, 3 三個點，隨機選一個選 1

將 1 印出，與 1 相接的有 0 和 5 但是 0 已經被印出過了，因此選擇 5

與 5 相鄰的有 1, 3, 4 其串 1 已經印出了，我們選擇 3

與 3 相鄰的有 0, 5 但兩個都已經被走訪了，因此我們回到前一個步驟

因為 3 的鄰點已經走訪過了，因此回到 5 來看一下發現 4 還沒走訪於是走訪 4

4 的鄰點 5 也走訪了，因此回到 5，5 的前一個走訪是 1，1 的前一個走訪是 0，0 有 1, 2, 3 3 個鄰點，只有 2 沒走，所以走訪 2

如何以程式實作 DFS？

從剛剛的走訪中可以發現，我們必需要想辦法

1. 知道哪個點有走過哪個點沒走過 (布林陣列或 map)
2. 能回到上一次所經過的點 (堆疊)

主程式會長這樣：

./lesson26.go

package main
import(
    "practice/graph"
    "fmt"
)

func main(){
    g  := graph.NewGraph()
    v0 := g.NewVertex(0)
    v1 := g.NewVertex(1)
    v2 := g.NewVertex(2)
    v3 := g.NewVertex(3)
    v4 := g.NewVertex(4)
    v5 := g.NewVertex(5)
    g.AddEdge(v0, v1)
    g.AddEdge(v0, v2)
    g.AddEdge(v0, v3)
    g.AddEdge(v1, v5)
    g.AddEdge(v3, v5)
    g.AddEdge(v4, v5)

    fmt.Println("簡單走訪")
    g.EasyTraversal()

    fmt.Println("DFS")
    g.DFS(v0)
}

因為還沒實作 DFS() 還不能執行
只是讓各位魔法使稍微了解一下用法

繼續實作 DFS (延續文章開頭的程式)
./graph/graph.go

首先因為我們會用到 stack，所以引入先前製作好的stack包，(如果沒有製作的人也可以先使用 Golang 提供的 list 包做練習)

import (
    "container/list"
    "fmt"
    "practice/stack"
)

func (g *Graph) DFS(start *Vertex){
    // 記錄誰有走訪誰沒有走訪
    visited := make(map[*Vertex]bool)
    // 宣告一個堆疊以方便回去前一步
    path_stack := stack.New()

    // 處理頭點
    path_stack.Push(start)
    visited[start] = true
    fmt.Printf("%v -> ", start.Val)

    // 疊出堆疊 第 12 行
    for v := path_stack.Pop(); v != nil; v = path_stack.Pop(){ // 第 13 行
        // 透過節點來走訪串列
        // element 是 list.Element
        for element := g.adj_list[v.(*Vertex)].Front(); element != nil; element = element.Next(){
            adj_v := element.Value.(*Vertex)
            // 若相鄰節點尚未被走訪
            if visited[adj_v] == false{
                // 原本第 13 行疊出的節點要記得疊入回去
                path_stack.Push(v)
                path_stack.Push(adj_v)
                visited[adj_v] = true
                fmt.Printf("%v -> ", adj_v.Val)
                // 離開走訪串列(因為是深度優先啊，所以找到新點後就改以新點為優先)
                // 而不是沉溺在這裡面
                // 回到走訪 g.adj_list
                break
            }
        }
    }
}

這裡的實作只呼叫一次 DFS() (搭配stack)即可完成，實作時，也可以改用 DFS() 呼叫另一個 DFS_recursive() 讓 DFS_recursive() 呼叫自己達到遞迴的效果。有點抽象，文末補充

執行 ./lesson26.go 的結果
簡單走訪
[3] -> 0 -> 5 -> nil
[4] -> 5 -> nil
[5] -> 1 -> 3 -> 4 -> nil
[0] -> 1 -> 2 -> 3 -> nil
[1] -> 0 -> 5 -> nil
[2] -> 0 -> nil
DFS
0 -> 1 -> 5 -> 3 -> 4 -> 2 ->

廣度優先搜尋 BFS (Breadth First Search)

BFS 與 DFS 的理念不同 DFS 是如果有新的相鄰節點就從該相鄰節點繼續往下找，而 BFS 不一樣，BFS 是把相鄰的點都先走一遍再隨便挑一個剛剛走過的往下走訪

一樣我們先從 0 開始

再來走訪 0 的鄰點 1, 2 , 3 (估且稱為第一輪)(實際上是看程式加入點的順序，但為了講解方便我們從數字小的開始走訪)

因為 0 的鄰點已經走訪完了，所以我們從第一輪最先加入的點 (1) 繼續走訪到 (5) (估且稱為第二輪)

因為 0 的鄰點已經走訪完了，所以我們從剛剛第一輪第二個加入的點 (2) 繼續走訪，但 (2) 的鄰點也走完了，所以從第一輪第三個加入的 (3) 走訪，第 (3) 的鄰點也走完了，因此我們只能從第二輪的 (5) 走訪，走訪到 (4)

如何以程式實作 BFS？

實作 BFS 時如同剛剛的 DFS 一樣一定要有個可以記錄的陣列或map，另一方面在每次走訪不到新點時一定要回到最開始的那個節點(比如走訪 1,2,3 後發現沒路了所以要回到 1 重新 BFS) 這種先進先出的概念非 Queue 莫屬

因為會用到 queue 所以添加先前實作出來的 package，如果沒有實作的朋友也可以直接拿 Golang 提供的 container/list 來用

Day23 課程：#23 佇列 Queue | Golang魔法使

繼續實作 BFS (延續DFS)
./graph/graph.go

package graph
import (
    "container/list"
    "fmt"
    "practice/stack"
    "practice/queue"
)

func (g *Graph) BFS(start *Vertex){
    // 記錄誰有走訪誰沒有走訪
    visited := make(map[*Vertex]bool)
    // 宣告一個佇列以方便查看要回到哪一步
    path_queue := queue.New()

    // 處理頭點
    path_queue.En(start)
    visited[start] = true
    fmt.Printf("%v -> ", start.Val)

    // 從佇列 De 出
    for v := path_queue.De(); v != nil; v = path_queue.De(){
        // 透過節點來走訪串列
        // element 是 list.Element
        for element := g.adj_list[v.(*Vertex)].Front(); element != nil; element = element.Next(){
            adj_v := element.Value.(*Vertex)
            // 若相鄰節點尚未被走訪
            if visited[adj_v] == false{
                path_queue.En(adj_v)
                visited[adj_v] = true
                fmt.Printf("%v -> ", adj_v.Val)
                // 因為是廣度優先所以要沉溺在這個 list 裡面
                // 不要 break 掉
            }
        }
    }
}

實際使用看看

本教學採用新的套件模式 (go version >= 1.11)
預設 module 名稱是 practice ，所以要 import "practice/graph"

• ./
  • go.mod (利用 go mod init 建立)
  • stack/
    • stack.go (先前課程創立的套件)
  • graph/
    • graph.go (剛剛創建的套件)
  • lesson26.go (準備調用)

./lesson26.go

package main
import(
    "practice/graph"
    "fmt"
)

func main(){
    g  := graph.NewGraph()
    v0 := g.NewVertex(0)
    v1 := g.NewVertex(1)
    v2 := g.NewVertex(2)
    v3 := g.NewVertex(3)
    v4 := g.NewVertex(4)
    v5 := g.NewVertex(5)
    g.AddEdge(v0, v1)
    g.AddEdge(v0, v2)
    g.AddEdge(v0, v3)
    g.AddEdge(v1, v5)
    g.AddEdge(v3, v5)
    g.AddEdge(v4, v5)

    fmt.Println("簡單走訪")
    g.EasyTraversal()

    fmt.Println()
    fmt.Println("DFS")
    g.DFS(v0)

    fmt.Println()
    fmt.Println()
    fmt.Println("BFS")
    g.BFS(v0)
}

執行結果：
簡單走訪
[5] -> 1 -> 3 -> 4 -> nil
[0] -> 1 -> 2 -> 3 -> nil
[1] -> 0 -> 5 -> nil
[2] -> 0 -> nil
[3] -> 0 -> 5 -> nil
[4] -> 5 -> nil

DFS
0 -> 1 -> 5 -> 3 -> 4 -> 2 ->

BFS
0 -> 1 -> 2 -> 3 -> 5 -> 4 ->

後記

這集為了不讓哥哥發現跑去出和Golang牌修幹，小櫻還用「鏡」做出一個假的自己讓她伴演生病的小櫻。

日本的小孩都這麼貼心的嘛？

要是我有「鏡」的話，學校的課都叫「鏡」去上不就好了嗎

本文大多數圖片來自：

• 庫洛魔法使第二季第四集

妹控桃矢果然不一樣

畢竟這傢伙曾經把他推下懸崖