---
tags: golang
---
# Let’s GO LeetCode: Week9 貪心

<!-- {%hackmd ByVnhRAIY %} -->

## Prim's Algorithm
普林演算法（Prim's algorithm），圖論中的一種演算法，可在加權連通圖里搜索最小生成樹
### Prim's Algorithm之演算法將使用三個資料項目

* ``predecessor[]``：記錄最後在MST中，各個vertex之間的「parent-child」關係。
* ``key[]``：此為「挑選edge」的關鍵，`key[]`記錄的會是edge的weight，但是會將weight「暫存在vertex上」，表示「到達該vertex的成本」，演算法的最後將挑選出能夠以「最低成本」抵達該vertex的edge，此edge上的兩個vertex即形成「parent-child」關係，能夠記錄進`predecessor[]`。
* `visited[]`：用來標記出，哪些vertex已經在MST裡面，哪些還沒有。已經是MST之vertex標記為1，其餘為0。

### 演算法步驟

#### 初始化
* ``predecessor[]``設成−1，表示vertex沒有predecessor。
* ``key[]``設成「無限大」，表示所有vertex都沒有辦法經由與其餘vertex相連之edge抵達。
* `visited[]`設成0，表示MST裡面還沒有vertex。
* (程式範例中，`visited[]`的資料型態是用`bool`，因此設為false)


#### 選擇起點
* 選定其中一個vertex作為起點。
* 這個起點會是MST的root，如果不要求MST之起點為何，那麼起點可以任意挑選。
* 在此選定vertex(2)作為起點，便將key[2]設成0。
* 更新`key[]`是關鍵，原因在於，演算法會根據`key[]`的大小，每次挑選出`key[]`值最小的vertex放進MST。

#### 主要部份
* 先從`key[]`中挑選出數值最小(可以想成「抵達成本」最小)的vertex，放進MST。
* 在此挑選到的是vertex(2)，見圖一\(c\)。
* 由於vertex(2)已經屬於MST，便更新visited[2]=1。

根據圖一\(c\)，與vertex(2)相連的vertex分別是vertex(1)、vertex(3)、vertex(6)，經比較後發現：

`weight(2,1)` < `key[1]`；
`weight(2,3)` < `key[3]`；
`weight(2,6)` < `key[6]`；
此時便更新`key[]`與 `predecessor[]`，見圖一(d)：

`key[1]`=`weight(2,1)`= 10，`predecessor[1]` = 2；
`key[3]`=`weight(2,3)`= 5，`predecessor[3]` = 2；
`key[6]`=`weight(2,6)`= 3，`predecessor[6]` = 2。


---

---

---

---

---

---

---

---

---

---

### code

package main

import (
    "fmt"
)

const maxWeight int = 1000

var adjMatrox = [][]int{}
var predecessor = []int{}
var key = []int{}
var visited = []bool{}
var numsVertex int

func init_tree(num_node int){
    numsVertex = num_node;
    adjMatrox = make([][]int, numsVertex)
    visited = make([]bool, numsVertex)
    predecessor = make([]int, numsVertex)
    key = make([]int, numsVertex)
    for i := 0; i < numsVertex; i++{
        adjMatrox[i] = make([]int, numsVertex)
    }
}

func add_edge(from, to, weight int){
    adjMatrox[from][to] = weight;
}

func minKeyExtract() int {
    min, min_idx := maxWeight, 0
    for i := 0; i < numsVertex; i++ {
        if(visited[i] == false && key[i] < min){
            min = key[i]
            min_idx = i
        }
    }
    return min_idx
}

func primMst(start int){
    for i := 0; i < numsVertex; i++ {
        key[i] = maxWeight
        visited[i] = false
    }

    key[start] = 0


    fmt.Println(1)
    for i := 0; i < numsVertex; i++{
        u := minKeyExtract()
        visited[u] = true;
        
        for j := 0; j < numsVertex; j++ {
            if(visited[j] == false && adjMatrox[u][j] != 0 && adjMatrox[u][j] < key[j]){
                predecessor[j] = u
                key[j] = adjMatrox[u][j]
            }
        }
    }
    fmt.Println(2)

    for i := (start + 1) % numsVertex; i != start; i = (i + 1) % numsVertex{
        fmt.Printf("v1: %d, v2: %d, weight: %d\n", predecessor[i],  i, adjMatrox[predecessor[i]][i])
    }
}

func main() {
    init_tree(7)
    add_edge(0, 1, 5);add_edge(0, 5, 3);
    add_edge(1, 0, 5);add_edge(1, 2, 10);add_edge(1, 4, 1);add_edge(1, 6, 4);
    add_edge(2, 1, 10);add_edge(2, 3, 5);add_edge(2, 6, 8);
    add_edge(3, 2, 5);add_edge(3, 4, 7);add_edge(3, 6, 9);
    add_edge(4, 1, 1);add_edge(4, 3, 7);add_edge(4, 5, 6);add_edge(4, 6, 2);
    add_edge(5, 0, 3);add_edge(5, 4, 6);
    add_edge(6, 1, 4);add_edge(6, 2, 8);add_edge(6, 3, 9);add_edge(6, 4, 2);
    primMst(2)
}

## Dijkstra
- 將所有頂點分為兩個部分
- 已知最短路徑的頂點集合
- 未知最短路徑的頂點集合
- 原點到自己的最短路徑為 0，如果原點能到其他點 i，則把距離存到 `dis[i]` 之中。不能到的點，距離為無限
- 在未知最短路徑的點中找一個頂點 u 離原點最近，以 u 為起點對其他邊進行檢查，比較從 s → u → v 的路徑能否比 s → v 短，可以的話則更新。(v 為 u 能到的某一點)

### 範例
#### 距離
| |1 |2 |3 |4 |5 |6|
|---|---|---|---|---|---|--|
|1 |0 |1 |12 |∞ |∞ |∞|
|2 |∞ |0 |9 |3 |∞ |∞|
|3 |∞ |∞ |0 |∞ |5 |∞|
|4 |∞ |∞ |4 |0 |13 |15|
|5 |∞ |∞ |∞ |∞ |0 |4|
|6 |∞ |∞ |∞ |∞ |∞ |0|

#### 從原點能到的最短距離
||1 |2 |3 |4 |5 |6|
|-|-|-|-|-|-|-|
|dis|0 |1 |12 |∞ |∞ |∞|

package main

import "fmt"

func isUnvisited(n int, unvisited map[int]bool) bool {
    for i, j := range unvisited {
        if n == i && j {
            return true
        }
    }
    return false
}
func main() {
    var tab [][]int
    var dis [7]int
    visited := make(map[int]bool)
    unvisited := make(map[int]bool)
    tab = append(tab, []int{1, 2, 1})
    tab = append(tab, []int{1, 3, 12})
    tab = append(tab, []int{2, 3, 9})
    tab = append(tab, []int{2, 4, 3})
    tab = append(tab, []int{3, 5, 5})
    tab = append(tab, []int{4, 3, 4})
    tab = append(tab, []int{4, 5, 13})
    tab = append(tab, []int{4, 6, 15})
    tab = append(tab, []int{5, 6, 4})

    for i := 2; i <= 6; i++ {
        unvisited[i] = true
        dis[i] = 100
    }

    for _, i := range tab {
        if i[0] == 1 {
            dis[i[1]] = i[2]
        }
    }
    dis[1] = 0
    visited[1] = true

    for len(unvisited) > 0 {
        fmt.Println(dis)
        fmt.Println(unvisited)
        var node int
        min := 100
        for i, j := range dis {
            if j < min && isUnvisited(i, unvisited) {
                node = i
                min = j
            }
        }
        fmt.Println(node)
        for _, i := range tab {
            if node == i[0] {
                //如果到 i[0] 的最短距離加上到 i[1] 的距離 i[2] 比目前到 i[1] 的距離還短的話
                if dis[i[0]]+i[2] < dis[i[1]] {
                    dis[i[1]] = dis[i[0]] + i[2]
                }
            }
        }
        delete(unvisited, node)
        visited[node] = true
    }

    fmt.Println(dis)

}