25年CH计算机科学与技术-无向图中最小生成树算法的时间复杂度对比分析-约9791字符终版.docx

I摘 要在图论的广阔领域中，最小生成树（MinimumSpanningTree,MST）问题占据着举足轻重的地位。对于一个连通无向图，其包含众多顶点与边，而最小生成树便是在这些元素中，选取包含所有顶点且边权和最小的子图。这一概念可形象地类比为城市间的交通网络建设，城市如同图中的顶点，连接城市的道路则是边，每条道路的建设成本或距离作为边的权重。在此情境下，最小生成树的目标就是找到一种道路建设方案，使得所有城市都能连通，同时建设总成本最低。为求解最小生成树问题，涌现出许多经典算法，其中 Prim 算法与Kruskal 算法尤为突出。Prim 算法采用从一个起始顶点开...