[筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 44

重念一次早該補起來的「資料結構與演算法」。這篇筆記下 Prim’s Algorithm 普林演算法

notes-theideaofalgorithm-javascript-1


課程相關資訊

[連結]:https://hiskio.com/courses/572/lectures/29887

本篇範圍:Chapter 9

請注意:本系列文章為個人對應課程的消化吸收後,所整理出來的內容。換言之,並不一定會包含全部的課程內容,也有可能會添加其他資源來說明。


內容

1. 要有 Visited Nodes 和 Edges,其中 Visited Nodes 必須要全部都有
2. 從任意的 Nodes 出發,開始觀察周圍的 Edges。當找到最小的 Edge 時,就選擇這一條,並將其兩端 Nodes 給記下來
3. 每當有記上一條 Edge 時,你會有新的 Node 進入你的觀察視野。觀察當下的所有與 Visited Nodes 相連的 Edge:在排除掉已經加入 Edge 清單的情況下,剩餘的 Edge 哪一個值最小。接著反覆重複過程,直到剩餘的 Edge 都會和 Visited Nodes 成 loop 為止

根據 Prim’s Algorithm,無論你從哪一個點開始找 Minimum Spanning Tree,結果都是一樣的。

判斷是否生成一個 Loop 的方法:當你找到一條 Edge,其兩端都已經在 Visited Nodes 的列表中了


程式碼

https://github.com/andy922200/hiskio-the-idea-of-algorithm/commit/8226a1ba1acb0ce4fe05df4ff5e6c7deba1e4974


系列文章

  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 9
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 8
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 7
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 6
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 59
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 58
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 57
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 56
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 55
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 54
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 53
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 52
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 51
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 50
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 5
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 49
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 48
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 47
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 46
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 45
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 43
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 42
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 41
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 40
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 4
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 39
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 38
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 37
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 36
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 35
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 34
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 33
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 32
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 31
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 30
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 3
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 29
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 28
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 27
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 26
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 25
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 24
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 23
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 22
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 21
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 20
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 2
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 19
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 18
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 17
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 16
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 15
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 14
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 13
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 12
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 11
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 10
  • [筆記] 程式必修課!資料結構與演算法|JavaScript 篇 – 1
  • 按讚加入粉絲團

    延伸閱讀