Graphic Theory: Chapter 8

Spanning tree: Tree T是graph G的spanning tree，如果T是G的subgraph且包含G的所有vertices的話
G為connected iff G擁有spanning tree。Spanning tree的數量不一定是1，但是如果G是tree的話，spanning tree的數量為1。
Cycle Cn的spanning tree數量為n。

Kirchhoff's matrix-tree theorem可以用來判斷，一個graph能夠建立出多少個spanning tree。請練習!

BFS和DFS可以用來建立spanning tree，只要在每次搜尋中連線還沒被連線過的點即可

(填寫adjacency list時，一次填一個row，左邊是連出的項(head)，右邊是被連的項(tail))

Minimum spanning tree

Prim's algorithm: 用來產生minimum spanning tree。但他好像不能找到所有spanning tree裡面最小的weight者阿，還是說他只能找到目前這個root的weight最小者？

Kruskal's algorithm: 每次選擇weight最小的邊且不會造成兩個重複的點加入。