有向图邻接矩阵实现与遍历

"有向网的邻接矩阵存储" 本文主要介绍了如何使用邻接矩阵来存储有向网络，并实现各种图的遍历操作，包括深度优先遍历和拓扑排序，以及计算最短路径。此外，还提供了输入输出的具体格式和示例数据。 在有向网络中，邻接矩阵是一种常用的数据结构，用于表示网络中各个节点之间的连接关系。对于一个有n个节点的网络，邻接矩阵是一个n×n的矩阵，其中的元素表示节点之间的边。如果节点i到节点j存在一条有向边，且这条边具有权值w，那么矩阵的第i行第j列的元素就是w；如果不存在边，则该位置的元素通常设置为0。 1. **邻接链表的建立与生成输出** 在邻接矩阵的实现中，通常会用链表来存储非零元素，因为这可以更有效地表示稀疏图（即含有较少边的图）。CreateAdjacencymatrix()函数负责构建邻接链表，每个链表节点包含边的终点索引和权值信息。通过遍历矩阵，找到非零元素，将其转化为链表结构，并输出邻接链表以验证图的正确性。 2. **深度优先遍历（DFS）** 深度优先遍历是图遍历的一种策略，它从一个节点开始，访问当前节点，然后递归地访问所有未访问过的相邻节点。在非递归实现中，可以使用栈来存储待访问的节点。DFSStack(int v)函数实现了这个过程，从节点v开始，将其压入栈中，然后不断弹出栈顶节点，访问并将其未访问的邻接节点压入栈，直到所有节点都被访问。 3. **拓扑排序** 拓扑排序是对有向无环图（DAG）的一种排序，使得对于每一条有向边u->v，节点u在排序后的序列中都出现在节点v之前。在给定的程序中，拓扑排序是通过模拟静态栈实现的，每次将入度为0的节点加入结果序列，并减少其邻接节点的入度。当所有节点都入度为0时，拓扑排序完成。 4. **计算最短路径** 程序还包括了计算从任一点到所有其他点的最短路径的功能。这可能使用了Dijkstra算法或Floyd-Warshall算法等经典算法。这些算法可以找出图中每对节点之间的最短路径，输出为一维数组形式。 测试数据示例： 给定一个包含4个节点（a, b, c, d）和5条边的有向图，程序首先输出邻接矩阵，然后输出非递归深度优先遍历的结果，接着是拓扑排序和最短路径。具体图形如下： ``` 0 1 2 3 ``` 边的连接关系为：0到1（权值8），0到2（权值6），0到3（权值7），1到3（权值5），2到3（权值4）。 总结，这个程序提供了对有向图的全面操作，包括存储、遍历、排序和路径查找，这些都是图论和算法学习中的基础内容，对于理解和处理复杂网络问题非常有帮助。