生成樹是否與遍歷演算法有關

1. 為什麼圖的bfs生成樹的樹高比dfs生成樹的樹小或相等

圖的bfs生成樹的樹高比dfs生成樹的樹小或相等的原因如下：

1、廣度優先搜索（BFS）和深度優先搜索（DFS）是兩種常見的圖遍歷演算法。

2、BFS是層序遍歷，每次都會把離根節點最近的節點先進行遍歷，這樣能夠保證搜索到的節點數目不會超過樹的深度，也就不會超過樹的最大高度。

3、DFS是遞歸進行的，它從根節點開始，沿著一個方向遍歷到不能再深入為止，然後回溯到之前的節點，再沿著另一個方向進行遍歷。這種方式可能會導致某些節點的多次遍歷，尤其是在一些復雜的樹或圖中，從而增加了生成樹的高度。

3、優化問題：在一些需要找出最優解的問題中，如找到一個圖中的最大權值或者最大價值，DFS也可以被應用。這是因為DFS在遍歷過程中會完整遍歷所有的路徑，然後回溯並選取最優的解。

4、圖的遍歷：BFS可以用於遍歷圖中的所有節點，查找特定節點或找到從起始節點到目標節點的最短路徑。

5、搜索最短路徑：BFS在尋找最短路徑問題上非常有效，因為它會逐層遍歷圖的節點，直到找到目標節點。

6、圖的連通性：BFS可以用於檢測圖是否連通，以及找到圖的連通分量。

7、生成樹：在生成樹演算法中，BFS也被用作一種高效的演算法，用於在加權無向圖中構造最小生成樹。

2. 普里姆演算法的相關概念

1）生成樹一個連通圖的生成樹是它的極小連通子圖，在n個頂點的情形下，有n-1條邊。生成樹是對連通圖而言的，是連通圖的極小連通子圖，包含圖中的所有頂點，有且僅有n-1條邊。非連通圖的生成樹則組成一個生成森林；若圖中有n個頂點，m個連通分量，則生成森林中有n-m條邊。
2）和樹的遍歷相似，若從圖中某頂點出發訪遍圖中每個頂點，且每個頂點僅訪問一次，此過程稱為圖的遍歷，(Traversing Graph)。圖的遍歷演算法是求解圖的連通性問題、拓撲排序和求關鍵路徑等演算法的基礎。圖的遍歷順序有兩種：深度優先搜索（DFS）和廣度優先搜索（BFS）。對每種搜索順序，訪問各頂點的順序也不是唯一的。
3）在一個無向連通圖G中，其所有頂點和遍歷該圖經過的所有邊所構成的子圖G′稱做圖G的生成樹。一個圖可以有多個生成樹，從不同的頂點出發，採用不同的遍歷順序，遍歷時所經過的邊也就不同。
在圖論中，常常將樹定義為一個無迴路連通圖。對於一個帶權的無向連通圖，其每個生成樹所有邊上的權值之和可能不同，我們把所有邊上權值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實際應用。例如，通訊線路鋪設造價最優問題就是一個最小生成樹問題。常見的求最小生成樹的方法有兩種：克魯斯卡爾(Kruskal)演算法和普里姆（Prim）演算法。

3. 連通圖用深度優先和廣度優先演算法所得的生成樹是否唯一

理論上遍歷所得的生成樹或序列是不唯一的，演算法本身並沒有對同等條件下哪個點優先訪問做要求。但實際寫代碼的時候肯定要按某種順序遍歷，通常是從小到大，這時首個訪問的點肯定是第一個點，當前點與多個未訪問點相連時也是優先訪問編號小的點，這樣所得的結果就是唯一的了。