這天國民女兒知世在合唱團練唱時，不幸遭受「圖」Golang牌攻擊，導致無法發出聲音。因此尋求怪醫黑捷克開刀，但怪醫黑捷克一口價三千萬，就算知世家在有錢也請不起。

各位魔法使們能一起幫助小櫻收服「圖」Golang牌嗎？

當小櫻朋友真滴很衰吔，不是被冰住(第1季第33集)，就是沒聲音(第2季第2集)，要不然就是遊樂園失火(第1季第35集)，甚至是摔下懸崖(第1季第25集 和 第1季第34集)

什麼是圖？

簡單來說，圖就是樹的進化版，圖的邊可以比樹跟樹的鍵結更隨易，幾乎沒有限制，可以有向可以無向，可以兩點間不只一條邊，甚至還可以在邊上設權重。

圖主要由兩個構造所構成分別為「點」和「邊」，其實跟樹非常像。「樹」可以說是圖的特例

圖的表示方式

記錄一張圖通常有兩種方式：Adjacency matrix, Adjacency list 前者比較簡單但很耗空間，由二維陣列(或切片)構成，後者比較抽象一點，是由陣列(或切片)配合鏈結列所構成。

因為這兩個名詞一般都是講英文，大家直接記得英文就好，中文就不用了

Adjacency Matirx

以最左邊的欄代表起點，最上邊的列代表終點，如果有一條邊符合就記錄為 1，沒有就記錄為 0，因為 0 太多了所以省略不填。

圖沒有規定兩個點間只有一條邊如果兩個點間有兩條邊，則可以記錄為 2，依此類推

Adjacency List

可以很明顯地看出這個二維陣列有值的部分並不多，如果用 Adjacency matrix 記錄更大張的圖，那麼會浪費更多空間。因此一般會推薦採用 Adjacency list

以左邊的陣列{0,1,2,3,4,5}為起始點，linked list 上的點為終點，形成 Ajacency list

建立一張 Ajacency list

1. 創立自訂 package

首先我們先創建一個 package，至於要怎麼創建？請複習：#14 套件 Package (2020) & 套件實戰(math, http, sort) | Golang魔法使

./graph/graph.go

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

type Graph struct{
    // 建立一個鏈結串列切片
    adj_list [](*list.List)
}

type Vertex struct{
    Val int
}

NewGraph() 和 NewVertex()

其中，在使用 NewGraph() 時告訴有幾個點

利用 NewVertex() 創立點

func NewGraph(number_of_node int) *Graph{
    g := new(Graph)
    g.adj_list = make([](*list.List), number_of_node)
    for k, _ := range g.adj_list{
        g.adj_list[k] = list.New()
    }
    return g
}

func NewVertex(number int) *Vertex{
    v := new(Vertex)
    v.Val = number
    return v
}

AddEdge()

允許使用者分別給定起始點和結束點建立一條邊

這部分很簡單，就是把「結束點」插在 Graph 的 adj_list[啟始點] 的前或後

func (g *Graph) AddEdge(start, end *Vertex){
    // list 包中的 PushBack() 可以在原有的串列後增加新的元素
    g.adj_list[start.Val].PushBack(end)
}

EasyTraversal()

因為建立完後看不到長怎樣，所以我們再簡單的把圖表中的資料印出來看一看

這種走訪沒什麼實際意義，只是方便我們 debug 一下

func (g *Graph) EasyTraversal(){
    // adj_list[index] 內存的是 *list.List
    // 利用 .Front() 可以取得頭點
    // 利用 .Next() 可以取得下個點
    // 在 list 包中節點的型態為 Element
    // 而利用 .Value 可以取得原先放進去的值該值為 interface{} (泛型)
    for k, v := range g.adj_list{
        fmt.Printf("[%d] -> ", k)
        for current := v.Front(); current != nil; current = current.Next(){
            // current.Value 為 interface{}
            // 利用 .(*Vertex) 斷言，告訴 Go 這是一個 *Vertex
            // 再對 *Vertex 取值
            fmt.Printf("%d -> ", current.Value.(*Vertex).Val)
        }
        fmt.Println("nil")
    }
}

其中，可能令人比較陌生的是「斷言」這種用法，這個是用來給 interface{} 型態使用，如果原先以 int 當 interface{} 來存，在取用時，必需先用 .(int) 來「轉」換型態。並不是每個情況取用都一定要轉，新手魔法使們多試幾次有噴錯就知道什麼時候要「斷言」了

2. 實際調用

實際調用：

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

• ./
  • go.mod (利用 go mod init 建立)
  • graph/
    • graph.go (剛剛創建的套件)
  • lesson25.go (準備調用)

./lesson25.go

package main
import(
    "practice/graph"
)

func main(){
    // 範例中有六個節點
    g  := graph.NewGraph(6)
    v0 := graph.NewVertex(0)
    v1 := graph.NewVertex(1)
    v2 := graph.NewVertex(2)
    v3 := graph.NewVertex(3)
    v4 := graph.NewVertex(4)
    v5 := graph.NewVertex(5)
    g.AddEdge(v0, v1)
    g.AddEdge(v0, v2)
    g.AddEdge(v2, v3)
    g.AddEdge(v2, v4)
    g.AddEdge(v3, v0)
    g.AddEdge(v3, v5)
    g.AddEdge(v4, v1)
    g.AddEdge(v4, v5)

    g.EasyTraversal()
}

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

有向圖與無向圖

剛剛介紹的圖是用鍵頭連結代表是有方向性的有向圖。如果單純以直線連接那麼就是無向圖，無向圖代表可以從直線的兩端是可以互通

↓ 這是一個無向圖

修改咒語(程式碼)來建立無向圖

修改 AddEdge() 使兩個方向都能互通

./graph/graph.go

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

重新執行 ./lesson25.go

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

如此一來，點和點間就能更簡單的往來，那為什麼要講無向圖呢？因為無向圖比較好走訪，為了明天的教學做準備

後記

小狼你是在害羞什麼，小櫻可是你的敵人吔

本集圖片來自：

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