基于邻接矩阵的近似Prim算法解决无向图特定问题

摘要

以消除无向连通图中构成环路的冗余边的算法为主线,引入并介绍了图形数据结构的逻辑结构和基本概念,通过对比分析图的几个常用存储结构的优缺点,确定选用邻接矩阵存储结构来存储无向连通图.详细分析如何利用近似Prim算法得到无向连通图的最小生成树,给出了算法的设计思路以及实现的方法和步骤,并给出通过广度优先搜索遍历实现该算法的C语言描述,最后对算法从时间复杂度和空间复杂度两个方面进行了评价.

关键词