C++实现邻接矩阵有向网操作：深度优先遍历与拓扑排序

"这篇文档是关于使用C++实现数据结构中的有向网，具体是通过邻接矩阵的方式来确定有向图，并实现了一系列相关操作，包括建立邻接链表、深度优先遍历、拓扑排序和最短路径计算。文档包含了需求分析、设计说明、主要数据结构设计以及程序的主要流程和模块函数。" 在C++中，数据结构是计算机科学的基础，而有向网是图论中的一个重要概念，表示顶点之间具有方向性的连接。邻接矩阵是一种存储有向图的有效方式，它是一个二维数组，其中的元素表示一对顶点之间是否存在边。如果存在，则元素值通常为非零，否则为零。 1. **需求分析**： - 运行环境：该程序在Windows 7系统上，使用Intel Core i5-2410M处理器和2GB内存，开发环境是Visual Studio 2008。 - 功能实现：包括构建邻接链表，非递归深度优先遍历，拓扑排序，以及最短路径计算。 - 输入：用户需提供节点数、顶点信息以及权值信息，权值信息以弧尾、弧头、权值的顺序输入，以000结束。 - 输出：包括邻接链表、深度优先遍历结果、拓扑排序结果和最短路径。 2. **设计说明**： - 算法思想：使用结构体存储边节点和顶点节点，邻接矩阵存储图，双层循环遍历，递归实现最短路径查找，拓扑排序优先处理入度为零的节点。 - 数据结构：包括图的邻接矩阵结构（顶点数、弧数、矩阵数组和点数组），栈结构（栈顶和栈底），点结构（顶点和与之相关的弧的指针信息）。 3. **程序流程**： - 程序主要包括创建有向网、打印邻接矩阵、打印邻接表、深度优先遍历、拓扑排序和计算最短路径等步骤。 4. **主要模块和函数**： - `CreatGraph`：创建有向网，读取节点数、顶点信息和权值，填充邻接矩阵。 - `PrintGraph`：输出邻接矩阵，显示图的结构。 - `PrintList`：打印邻接表，展示图的链表形式。 - 深度优先遍历和拓扑排序的函数未在文档中详述，但通常会包括递归或栈操作，以及更新入度和调整节点顺序。 5. **测试数据**： - 节点数5个，顶点为abcde。 - 权值信息定义了各顶点之间的边及其权重。 这个C++程序旨在提供一个完整的有向网操作工具，通过邻接矩阵实现，能够进行多种图的操作，如构建、遍历和排序，以及找到最短路径。这对于理解和应用图论概念，以及在实际问题中解决路径问题非常有用。