下列有關擴張樹(Spanning Tree)的敘述何者錯誤？

錯誤選項解析

• ① 一個圖形可能有許多個的擴張樹:擴張樹是包含圖中所有頂點且無環路的連通子圖，當圖中存在多個不同的邊組合可滿足此條件時，便會產生多個擴張樹，此敘述正確。
• ③ 圖形有n個節點與e 個邊，若以相鄰矩陣(Adjacency Matrix)表示，則利用深度優先搜尋(Depth-First Search)得出擴張樹的時間複雜度(Time Complexity)為O(n 2):使用相鄰矩陣進行 DFS 時，每個頂點需掃描整列（n 個元素），共 n 個頂點，故時間複雜度為 O(n²)，此敘述正確。
• ④ 圖形有n 個節點與e 個邊，若以相鄰串列(Adjacency Link)表示，則利用深度優先搜尋(Depth-First Search)得出擴張樹的時間複雜度(Time Complexity)為O(e):使用相鄰串列進行 DFS 時，每個頂點與其相鄰邊各被拜訪一次，時間複雜度為 O(n+e)，對連通圖而言 e≥n-1，可簡化為 O(e)，此敘述正確。