Data Structure
  • 資料結構自學筆記
  • 1 - Stack & Queue
    • 1.1 - Stack
    • 1.2 - Queue
    • 1.3 - Stack and Queue
  • 2 - Tree & Binary Tree
    • 2.1 - Tree
    • 2.2 - Binary Tree
    • 2.3 - Binary Tree Traversal
    • 2.4 - Binary Search Tree
    • 2.5 - Heap
    • 2.6 - Thread Binary Tree
    • 2.7 - Tree and Binary Tree Conversion
    • 2.8 Advanced Trees
      • 2.8.1 - Min-Max Heap
      • 2.8.2 - Deap
      • 2.8.3 - Symmetric Min-Max Heap
      • 2.8.4 - Extended Binary Tree
      • 2.8.5 - AVL Tree
      • 2.8.6 - M-Way Search Tree
      • 2.8.7 - B Tree
      • 2.8.8 - Red-Black Tree
      • 2.8.9 - Optimal Binary Search Tree
      • 2.8.10 - Splay Tree
      • 2.8.11 - Leftest Heap
      • 2.8.12 - Binomial Heap
  • 3 - Search & Sort
    • 3.1 - Searching
    • 3.2 - Elementary Sorting
      • 3.2.1 - Insertion Sort
      • 3.2.2 - Selection Sort
      • 3.2.3 - Bubble Sort
      • 3.2.4 - Shell Sort
    • 3.3 - Sophisticated Sorting
      • 3.3.1 - Quick Sort
      • 3.3.2 - Merge Sort
      • 3.3.3 - Heap Sort
      • 3.3.4 - Radix Sort
      • 3.3.5 - Bucket Sort
      • 3.3.6 - Counting Sort
    • 3.4 - Summary
  • 4 - Graph
    • 4.1 - Intro
    • 4.2 - Graph Traversal
    • 4.3 - Spanning Tree
      • 4.3.1 - Kruskal's algorithm
      • 4.3.2 - Prim's algorithm
      • 4.3.3 - Sollin's algorithm
    • 4.4 - Shortest Path Length
      • 4.4.1 - Dijkstra's algorithm
      • 4.4.2 - Bellman-Ford algorithm
      • 4.4.3 - Floyd-Warshall algorithm
    • 4.5 - AOV Network
    • 4.6 - AOE Network
    • 4.7 - Others
Powered by GitBook
On this page
  • 1. Spanning Tree
  • 2. Min Spanning Tree(最小成本展開樹)
  1. 4 - Graph

4.3 - Spanning Tree

Previous4.2 - Graph TraversalNext4.3.1 - Kruskal's algorithm

Last updated 6 years ago

1. Spanning Tree

G=(V,E)G=(V, E)G=(V,E) 是一個Connected的Undirected Graph，令 S=(V,T)S=(V, T)S=(V,T)是G的一個Spanning Tree:

  1. E=T+B⇒T=E−BE=T+B \Rightarrow T=E-BE=T+B⇒T=E−B

    T: Tree edge；B: Back edge

  2. 自B中挑選一個邊加入S中，必在S中形成一個cycle。

  3. 在S中的任何頂點對之間，存在一條唯一的Simple Path。

e.g.

  1. 任何Connected Undirected Graph至少有一棵Spanning Tree

  2. 若Connected Undirected Graph有v個頂點，則Spanning Tree的邊數必為v-1條邊

  3. 若將Binary Tree視為無向圖，則它的Spanning Tree只有一棵

  4. 若為unconnected graph，則必無Spanning Tree

2. Min Spanning Tree(最小成本展開樹)

Connected Undirected Graph G=(V,E)G=(V, E)G=(V,E) 的每個邊上cost值，則在Ｇ的所有spanning trees中具有邊成本總和最小者。

  1. min spanning tree ≥ 1

  2. 若G中每個邊的成本皆不同，則最小成本展開數樹只有一棵

求法:

  1. Kruskal's algorithm

  2. Prim's algorithm

  3. Sollin's algorithm

DFS Spanning Tree BFS Spanning Tree