⑴ 克魯斯卡爾和迪傑斯特拉演算法區別
克魯斯卡爾演算法和迪傑斯特拉演算法是兩種常用的圖演算法，主要區別如下：
1. 目標不同： - 克魯斯卡爾演算法用於求解最小生成樹問題（即連接所有節點的邊的權重之和最小），適用於無向加權圖。 - 迪傑斯特拉演算法用於求解單源最短路徑問題（即從一個源節點到其他所有節點的最短路徑），適用於有向或無向帶權圖。
2. 邊的處理方式不同： - 克魯斯卡爾演算法通過不斷選擇權重最小的邊，並將邊加入最小生成樹中，直到連接所有節點。 - 迪傑斯特拉演算法通過不斷選擇當前距離源節點最近的節點，並更新其鄰居節點的距離，直到求解出所有節點到源節點的最短路徑。
3. 數據結構和時間復雜度不同： - 克魯斯卡爾演算法通常使用並查集來判定邊的兩個節點是否處於同一個連通分量中，時間復雜度為O(ElogE)。 - 迪傑斯特拉演算法通常使用優先隊列（如最小堆）來實現比較和選擇當前距離源節點最近的節點，時間復雜度為O((|V|+|E|)log|V|)。總結來說，克魯斯卡爾演算法解決的是最小生成樹問題，迪傑斯特拉演算法解決的是單源最短路徑問題。兩者的核心思想和操作方式有所不同，適用場景也不同。