# 資料結構(0516)

## 班級 學號 姓名

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


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


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


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

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];
}


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

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];
}


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

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 檔寄至 [[e-mail]]([e-mail])
> 主旨：資料結構(0516)
> 內文：本週上課心得(100字以內)或省略
> 附件：資料結構(0516) - HackMD.pdf
> 注意：請修改**班級**、**學號**、**姓名**