---
# System prepended metadata

title: 資料結構(0516)

---

# 資料結構(0516)

## 班級 學號 姓名

### 最小擴張樹(Mininal Spanning Tree)

![Kruskal](https://hackmd.io/_uploads/SJPdjO4bxe.png)

1. 寫出Kruskal演算法並以此法求Fig.1的最小擴張樹。

![Prim](https://hackmd.io/_uploads/rJ4YjdEbxx.png)

2. 寫出Prim演算法並以此法求Fig.1的最小擴張樹。

![Sollin](https://hackmd.io/_uploads/HkbcsO4-el.png)

3. 寫出Sollin演算法並以此法求Fig.1的最小擴張樹。

```graphviz
graph G {
    labelloc="b";
    label="Fig. 1 Minimal Spanning Tree";
    rankdir = "LR";
    1 -- 2 [label = 38];
    1 -- 6 [label = 4];
    2 -- 3 [label = 13];
    2 -- 7 [label = 11];
    3 -- 4 [label = 9];
    4 -- 5 [label = 18];
    4 -- 7 [label = 15];
    5 -- 6 [label = 27];
    5 -- 7 [label = 22];
}
```

![Dijkstra](https://hackmd.io/_uploads/Bk0qou4Zge.png)

4. [Dijkstra's Algorithm]利用下面影片，求Fig.2由頂點1至其它頂點的最短路徑。
https://www.youtube.com/watch?v=8Ls1RqHCOPw

```graphviz
digraph G {
    labelloc="b";
    label="Fig. 2 Shortest Path";
    rankdir = "LR";
    1 -> 2 [label = 38];
    1 -> 6 [label = 4];
    2 -> 3 [label = 13];
    2 -> 6 [label = 12];
    2 -> 7 [label = 11];
    3 -> 4 [label = 9];
    3 -> 7 [label = 8];
    5 -> 4 [label = 18];
    6 -> 2 [label = 6];
    6 -> 5 [label = 27];
    7 -> 4 [label = 15];
    7 -> 5 [label = 22];
}
```

![Floyd](https://hackmd.io/_uploads/H1Fisd4Zeg.png)

5. [Floyd Algorithm]求Fig.3各頂點之間的最短距離。

```graphviz
digraph G {
    labelloc="b";
    label="Fig. 3 All Path Shortest Path";
    rankdir = "LR";
    1 -> 2 [label = 4];
    1 -> 3 [label = 11];
    2 -> 3 [label = 2];
    2 -> 1 [label = 7];    
    3 -> 1 [label = 1];
}
```

---

> 繳交作業請將 PDF 檔寄至 [lenghs@cc.ncue.edu.tw](lenghs@cc.ncue.edu.tw)
> 主旨：資料結構(0516)
> 內文：本週上課心得(100字以內)或省略
> 附件：資料結構(0516) - HackMD.pdf
> 注意：請修改**班級**、**學號**、**姓名**