C++实现：邻接矩阵与邻接表的无向图/有向图构造与输出

在严蔚敏编著的《数据结构》中，图的邻接矩阵和邻接表是介绍数据结构课程时常用的两种表示图的数据结构。本篇文档提供了针对C++初学者的实例代码，主要讲解如何在C++中建立并输出四种类型的图：无向图、有向图、无向网和有向网。以下是详细的知识点解析： 1. **邻接矩阵**： 邻接矩阵是一种用二维数组表示图的方法，其中行代表起点，列代表终点，矩阵中的元素值表示两个顶点之间是否存在边以及边的属性（如权重）。对于无向图，矩阵是对称的，即(i, j)位置的元素和(j, i)位置的元素相同；对于有向图，只有从i到j的边才会在(i, j)位置存储。 代码中定义了`AdjMatrix`结构体，用于存储每条边的邻接关系和相关信息。`StatusCreateDN`函数首先获取用户输入的图参数，如顶点数、边数、图的类型（有向图或有向网）以及弧是否有信息。然后，它通过循环构建顶点向量，并初始化邻接矩阵，对于带权图，还会处理弧的相关信息。 2. **邻接表**： 相比邻接矩阵，邻接表通常更节省空间，特别适合稀疏图（边的数量远小于可能的最大边数）。邻接表由每个顶点的邻接顶点列表组成，列表中包含指向其他顶点的边信息。在C++中，这可能使用链表或其他动态数据结构实现，但文档中并未提供邻接表的具体实现。 3. **图的创建与输出**： 在提供的代码中，`StatusCreateDN`函数负责整个图的创建过程。首先读取用户输入，接着构造顶点向量，然后根据用户指定的图类型（有向图或有向网）和边的信息类型（无权或有权），填充邻接矩阵。对于无向图，需要额外确保矩阵的对称性。最后，可能会有一个函数用于输出图的信息，包括顶点和边的数量等。 4. **函数`StatusLocateVex`**： 这个函数用于查找给定顶点在顶点向量中的索引，以便后续操作，如访问邻接矩阵或执行图的操作。 5. **图的类型和相关标志**： `GraphKind`枚举类型用于表示图的种类，UDN代表无向图，DN代表有向图。`inf`变量则用于标识边是否有权重。 这个文档为C++初学者提供了一个实用的例子，展示了如何使用邻接矩阵来表示和操作图，包括顶点的添加、边的连接以及基本的图结构创建和输出。通过这个实例，学习者可以理解邻接矩阵的基本概念，并进一步探索邻接表等其他图的表示方法。