幾個(gè)概念：有向圖、無(wú)向圖、加權(quán)圖、簡(jiǎn)單圖、聯(lián)通、聯(lián)通分量、生成樹(shù)、強(qiáng)連通分量、強(qiáng)聯(lián)通圖
圖的存儲(chǔ)：鄰接矩陣（二維、一維）、鄰接表
圖的遍歷：深搜、廣搜
（無(wú)向加權(quán)圖）最小生成樹(shù)：kruskal算法過(guò)程及證明、prime算法過(guò)程
單源最短距離問(wèn)題：dijkstra算法
深搜和回溯的區(qū)別：個(gè)人理解是深搜是圖的一種遍歷方式（樹(shù)也屬于圖），回溯是只用于樹(shù)

package main

import (
    "fmt"
    "math"
    "sort"
    "strconv"
)

func main() {
    vertexes := []string{"A", "B", "C", "D", "E", "F"}
    edges := []string{
        "AB,4", "AC,8", "AD,45", "AF,3",
        "BA,4", "BC,14", "BE,20", "BF,5",
        "CA,8", "CB,14", "CD,28", "CE,9",
        "DA,45", "DC,28", "DE,10",
        "EB,20", "EC,9", "EF,13", "ED,10",
        "FA,3", "FB,5", "FE,13",
    }
    g := NewGraph(vertexes, edges)

    g.DFS()
    g.BFS(0)
    g.Kruskal()
    g.Prime(0)
    g.Dijkstra(0)
}

type Vertex struct {
    Name      string
    FirstEdge *Edge
}

type Edge struct {
    V        int
    W        int
    Cost     int
    NextEdge *Edge
}

type Graph struct {
    VertexNum    int
    EdgeNum      int
    AdjacentList []Vertex
}

func NewGraph(vertexes []string, edges []string) Graph {
    g := Graph{}
    g.VertexNum = len(vertexes)
    g.EdgeNum = len(edges) / 2 // 無(wú)向圖
    g.AdjacentList = make([]Vertex, len(vertexes))

    m := map[string]int{}
    for i, vertex := range vertexes {
        v := Vertex{
            Name: vertex,
        }
        g.AdjacentList[i] = v
        m[vertex] = i
    }

    for _, edgeStr := range edges {
        v := m[string(edgeStr[0])]
        w := m[string(edgeStr[1])]
        cost, _ := strconv.Atoi(edgeStr[3:])
        edge := Edge{
            V:        v,
            W:        w,
            Cost:     cost,
            NextEdge: g.AdjacentList[v].FirstEdge,
        }
        g.AdjacentList[v].FirstEdge = &edge
    }

    return g
}

func (g *Graph) DFS() {
    visited := map[int]bool{}
    for i, _ := range g.AdjacentList {
        g.dfs(i, visited)
    }
}

func (g *Graph) dfs(v int, visited map[int]bool) {
    if visited[v] {
        return
    }
    vertex := g.AdjacentList[v]
    visited[v] = true
    fmt.Println("先深遍歷", vertex.Name)

    edge := vertex.FirstEdge
    for edge != nil {
        if visited[edge.W] {
            edge = edge.NextEdge
            continue
        }
        g.dfs(edge.W, visited)
    }
}

func (g *Graph) BFS(start int) {
    visited := map[int]bool{}

    var queue = []int{
        start,
    }

    i := 0
    for ; i < len(queue); i++ {
        k := queue[i]
        vertex := g.AdjacentList[k]
        if visited[k] {
            continue
        }
        fmt.Println("先廣遍歷", vertex.Name)
        visited[k] = true

        edge := vertex.FirstEdge
        for edge != nil {
            if !visited[edge.W] {
                queue = append(queue, edge.W)
            }
            edge = edge.NextEdge
        }
    }
}

func (g *Graph) Kruskal() (mst []Edge) {
    sortedEdges := g.sortEdges()
    mst = make([]Edge, g.VertexNum-1)

    i := 0
    l := 0
    selectedVertexes := map[int]bool{}

    for l < g.VertexNum-1 {
        edge := sortedEdges[i]
        if !(selectedVertexes[edge.V] && selectedVertexes[edge.W]) {
            selectedVertexes[edge.V] = true
            selectedVertexes[edge.W] = true
            mst[l] = edge
            l++
        }
        i++
    }

    fmt.Println("Kruskal結(jié)果")
    for _, edge := range mst {
        fmt.Println(g.AdjacentList[edge.V].Name+g.AdjacentList[edge.W].Name, edge.Cost)
    }

    return
}

func (g *Graph) sortEdges() []Edge {
    visited := map[int]bool{}

    edges := make([]Edge, g.EdgeNum)
    l := 0
    for i, vertex := range g.AdjacentList {
        edge := vertex.FirstEdge
        for edge != nil {
            if !visited[edge.W] {
                edges[l] = *edge
                l++
            }
            edge = edge.NextEdge
        }
        visited[i] = true
    }

    sort.Slice(edges, func(i, j int) bool {
        return edges[i].Cost < edges[j].Cost
    })

    return edges
}

func (g *Graph) Prime(start int) (mst []Edge) {
    fmt.Println("prime計(jì)算過(guò)程")
    selectedVertex := map[int]bool{start: true}
    unSelectedVertex := map[int]Edge{}

    lastSelectVertex := start
    for len(mst) < g.VertexNum-1 {
        var minCost = math.MaxInt64
        var minEdge Edge

        for i, _ := range g.AdjacentList {
            if selectedVertex[i] {
                continue
            }
            newCost, _ := g.getCost(lastSelectVertex, i)
            if edge, initialized := unSelectedVertex[i]; !initialized || newCost < edge.Cost {
                unSelectedVertex[i] = Edge{
                    V:    lastSelectVertex,
                    W:    i,
                    Cost: newCost,
                }
            }

            if unSelectedVertex[i].Cost < minCost {
                minCost = unSelectedVertex[i].Cost
                minEdge = unSelectedVertex[i]
            }
        }

        fmt.Println()
        for i, edge := range unSelectedVertex {
            if selectedVertex[edge.W] {
                continue
            }
            fmt.Println(i, g.AdjacentList[edge.V].Name+g.AdjacentList[edge.W].Name, edge.Cost)
        }
        fmt.Println("選擇最小邊: ", 
g.AdjacentList[minEdge.V].Name+g.AdjacentList[minEdge.W].Name, minEdge.Cost)

        mst = append(mst, minEdge)
        lastSelectVertex = minEdge.W
        selectedVertex[minEdge.W] = true
    }

    fmt.Println("最終結(jié)果")
    for i, edge := range mst {
        fmt.Println(i, g.AdjacentList[edge.V].Name+g.AdjacentList[edge.W].Name, edge.Cost)
    }

    return
}

func (g *Graph) getVertex(i int) Vertex {
    return g.AdjacentList[i]
}

func (g *Graph) getCost(from int, to int) (cost int, isInfinity bool) {
    startVertex := g.AdjacentList[from]
    edge := startVertex.FirstEdge
    for edge != nil {
        if edge.W == to {
            return edge.Cost, false
        }
        edge = edge.NextEdge
    }
    return math.MaxInt64, true
}

func (g *Graph) Dijkstra(start int) {
    fmt.Println("dijkstra計(jì)算過(guò)程")
    type vertexRecord struct {
        path     string
        cost     int
        selected bool
    }

    vertexes := make([]vertexRecord, g.VertexNum)

    for i, _ := range g.AdjacentList {
        if i == start {
            vertexes[start] = vertexRecord{
                path:     g.getVertex(start).Name,
                cost:     0,
                selected: true,
            }
            continue
        }
        cost, _ := g.getCost(start, i)
        vertexes[i] = vertexRecord{
            path: g.getVertex(start).Name + g.getVertex(i).Name,
            cost: cost,
        }
    }

    lastSelect := start
    for i := 0; i < g.VertexNum-1; i++ {
        minCost := math.MaxInt64
        minCostVertex := 0
        for j, _ := range vertexes {
            if vertexes[j].selected {
                continue
            }
            lastSelectVertex := vertexes[lastSelect]

            cost, isInfinity := g.getCost(lastSelect, j)
            if !isInfinity && lastSelectVertex.cost+cost < vertexes[j].cost {
                vertexes[j].cost = lastSelectVertex.cost + cost
                vertexes[j].path = lastSelectVertex.path + g.getVertex(j).Name
            }

            fmt.Println(fmt.Sprintf(`A到%s最近的路徑是%s，其耗費(fèi)是%d`,
 g.getVertex(j).Name, vertexes[j].path, vertexes[j].cost))
            if vertexes[j].cost < minCost {
                minCost = vertexes[j].cost
                minCostVertex = j
            }
        }
        fmt.Println()
        fmt.Println("本次最短路徑為", vertexes[minCostVertex].path, vertexes[minCostVertex].cost)
        fmt.Println()

        vertexes[minCostVertex].selected = true
        lastSelect = minCostVertex
    }

    for i, vertex := range vertexes {
        fmt.Println(i, vertex.path, vertex.cost)
    }
}