构建图的邻接表与邻接矩阵实现

"严蔚敏教材 习题集答案 第七章 图" 在计算机科学中，图是一种非常重要的数据结构，用于表示对象之间的关系。在严蔚敏教授的教材中，第七章专门讨论了图的相关概念和操作。这部分内容涵盖了有向图的构建以及邻接表和邻接矩阵两种图的表示方法。 7.14 题目涉及的是构建有向图的邻接表（Adjacency List）的过程。`Build_AdjList`函数首先初始化一个空的图`G`，然后读取图的顶点数`v`和边数`a`。接着，函数输入每个顶点的符号，并通过循环遍历边的信息，将边的起点（弧尾`t`）和终点（弧头`h`）连接起来。这个过程通过动态分配内存来创建新的弧节点，并将其插入到相应的顶点邻接表中。如果遇到无效的输入（如负数顶点数或边数，或者找不到的顶点），函数会返回错误状态。 7.15 题目则关注于在邻接矩阵表示的有向无权图中插入顶点和边的操作。`Insert_Vex`函数首先检查图的顶点数是否超过最大限制，如果没有，则将新的顶点`v`添加到图的顶点数组`G.vexs`中。`Insert_Arc`函数则需要查找两个顶点在图中的位置`i`和`j`，如果顶点存在且它们不相同，那么在邻接矩阵的对应位置插入边。这里，如果当前位置的值为`NULL`（表示还没有边），则创建一个新的边。 邻接表和邻接矩阵是图的两种常见表示方式。邻接表适用于稀疏图（边数远小于顶点数的平方），它以链表的形式存储每个顶点的邻接点，节省空间。而邻接矩阵则适合于稠密图（边数接近顶点数的平方），它用二维数组直接表示任意两个顶点之间是否有边相连，查询效率高但空间开销大。 在实际编程中，根据图的特点选择合适的表示方法是非常关键的。例如，对于社交网络这种可能存在大量边但大部分顶点之间并无连接的情况，使用邻接表更为合适。而对于电路设计等场景，由于节点间的连接可能非常频繁，邻接矩阵可能是更好的选择。理解这两种表示方法的优缺点并能灵活运用，是学习图论和算法的重要基础。