构建图的邻接表与邻接矩阵方法

"师傅的说法" 本文将探讨两个与图数据结构相关的函数，它们分别用于有向图的邻接表构建和邻接矩阵图的顶点与边的插入。这两个函数对于理解和操作图算法至关重要。 首先，我们来看7.14章节的`StatusBuild_AdjList(ALGraph &G)`函数，该函数用于根据输入的数据创建一个有向图的邻接表表示。邻接表是一种节省空间的图数据结构，尤其适用于稀疏图（边数远小于顶点数的平方）。函数首先初始化图`G`，接着读取顶点数`v`和边数`a`，确保它们非负。然后，它逐个读取顶点的符号信息，并通过两遍循环来构建邻接表。第一遍循环用于读取每个顶点的符号，第二遍循环处理边的信息，其中`t`表示弧尾，`h`表示弧头。函数通过`LocateVex`定位到弧尾和弧头对应的顶点，创建新的边节点`p`并将其插入到弧尾的邻接表中。如果在过程中遇到任何错误（如顶点未找到或内存分配失败），函数会返回错误状态。 接下来，7.15章节介绍的是在邻接矩阵表示的图`MGraph`中插入顶点和边的函数。`StatusInsert_Vex(MGraph &G, char v)`函数简单地在图的顶点数组`G.vexs`中插入新顶点`v`，但要注意防止超过预设的最大顶点数`MAX_VERTEX_NUM`。`StatusInsert_Arc(MGraph &G, char v, char w)`函数则负责插入一条从顶点`v`到`w`的边。函数首先通过`LocateVex`找到对应顶点，然后检查插入的边是否是自环（即顶点`v`和`w`相同），如果是，则返回错误。若顶点存在且不是自环，那么在邻接矩阵的对应位置插入一条边（在二维数组`G.arcs`中设置值）。 在实际应用中，邻接表和邻接矩阵是图数据结构的两种主要表示方式，各有优劣。邻接表适合处理稀疏图，空间效率高，而邻接矩阵则操作简便，便于查询任意两点之间是否存在边。因此，选择哪种表示通常取决于图的特性及所需执行的操作。了解这些基础函数有助于理解和实现图算法，如深度优先搜索、广度优先搜索、最短路径算法等。