使用邻接矩阵表示带权无向图并判断连通性

"这篇文章主要介绍了如何使用邻接矩阵表示带权无向图，并实现判断图是否连通以及求解最小生成树的Prim算法。" 在数据结构中，图是一种非常重要的数据结构，它可以用于表示各种关系。无向图是其中的一种，其中的边没有方向，即任意两个顶点之间可以互相到达。带权无向图则进一步地，每条边都赋予了一个权重或代价。在本例中，我们使用邻接矩阵来表示这种图。 邻接矩阵是一个二维数组，用来存储图中所有顶点之间的关系。对于无向图，邻接矩阵是对称的，即矩阵的第i行第j列和第j行第i列的元素相等，表示节点i到节点j的边的权重。如果两个节点之间没有边，则相应位置的元素通常设置为一个极大的值（如这里使用的`int_max`）或者无穷大（`inf`）来表示。 在给定的代码中，`AdjMatrix`结构体定义了一个邻接矩阵，其中`ArcCell`结构体用于存储边的信息，包括相邻节点的索引`adj`和附加信息`info`。`MGraph_L`结构体表示整个图，包括顶点数组`vexs`、邻接矩阵`arcs`、顶点数量`vexnum`和边的数量`arcnum`。 为了创建一个带权无向图，`createMGraph_L`函数首先读取用户输入的顶点数和边数，然后遍历输入的每个顶点和边，将它们存储在邻接矩阵中。`LocateVex`函数用于根据顶点名称找到其在顶点数组中的位置。 接着，我们要判断这个图是否连通。连通图是指图中任意两个顶点之间都存在路径。一种简单的判断方法是使用深度优先搜索（DFS）或广度优先搜索（BFS），遍历所有顶点，如果能从任一顶点到达其他所有顶点，则图是连通的。 最后，如果图是连通的，我们可以使用Prim算法求解最小生成树。Prim算法是从一个初始顶点开始，逐步添加边来构建一棵包含所有顶点且总权重尽可能小的树。每次选择当前未加入树中的边中权重最小的一条，使得加入这棵树后依然保持树的特性。这个过程可以使用优先队列（如二叉堆）来优化查找最小权重边的操作。 在代码中，这部分可能包含以下步骤： 1. 初始化一个空的最小生成树，将任意一个顶点加入树中。 2. 创建一个优先队列，用于存储待考虑的边及其权重。 3. 遍历图中所有与已加入树的顶点相邻的边，将这些边及其权重加入优先队列。 4. 在优先队列中取出权重最小的边，检查这条边是否连接了两个不同的树（即两个顶点不在同一棵子树中）。如果是，则将这条边加入最小生成树，并更新优先队列。 5. 重复步骤4，直到所有顶点都被加入最小生成树。 这个过程会继续进行，直到所有顶点都在同一棵生成树中，此时生成树的边就是最小生成树的边。 这篇文章涉及的知识点包括：邻接矩阵表示图、无向图、带权图、图的连通性判断、Prim算法求最小生成树以及相关的数据结构操作，如顶点和边的表示、优先队列的使用等。