数据结构_图的基本运算代码

#include"MGraph.h" #define INFTY 1000 template<class T> struct ENode { ENode() {nextArc=NULL;} ENode(int vertex,T weight,ENode *next) { adjVex=vertex; w=weight; nextArc=next; } int adjVex; T w; ENode* nextArc; }; 数据结构中的图是一种重要的抽象数据类型，用于表示对象之间的关系。在给定的代码中，主要涉及了图的基本运算，包括深度优先搜索（DFS）、广度优先搜索（BFS）以及拓扑排序。这里我们将详细解释这些概念以及相关代码实现。 1. **图的基本结构**： 在代码中，`ENode` 结构体定义了图的边，它包含了邻接顶点（adjVex）、权重（w）和指向下一个边的指针（nextArc）。`MGraph` 类和 `LGraph` 类是图的两种不同表示方式，其中 `MGraph` 通常用于表示无向图，而 `LGraph` 用于表示有向图。`ExtLGraph` 和 `ExtMGraph` 是对 `LGraph` 和 `MGraph` 的扩展，增加了基本的图操作。 2. **深度优先搜索 (DFS)**： DFS 是一种遍历或搜索树或图的方法，从一个节点开始，探索尽可能深的分支。在 `ExtLGraph` 类中，`DFS()` 函数实现了这个操作。它使用一个布尔数组 `visited` 记录每个顶点是否已被访问。对于每个未访问过的顶点，调用 `DFS(int v, bool *visited)` 函数进行递归遍历。在该函数中，首先标记当前顶点为已访问，然后对每条与当前顶点相邻的边，如果其邻接顶点未被访问，则递归调用 `DFS()`。 3. **广度优先搜索 (BFS)**： BFS 是另一种遍历或搜索树或图的方法，从一个节点开始，逐层地访问所有相邻节点。在 `ExtLGraph` 类中，`BFS()` 函数实现了这个操作。同样使用 `visited` 数组记录访问状态，但这次使用顺序队列 `SeqQueue` 存储待访问的顶点。从初始顶点开始，将其加入队列，并标记为已访问。然后，循环处理队列，每次取出队首元素，访问其所有未访问的邻接顶点，将它们加入队列。 4. **拓扑排序**： 拓扑排序是对有向无环图 (DAG) 的一种排序，使得对于任何边 `(u, v)`，`u` 总是在 `v` 之前。在 `ExtLGraph` 类的 `TopoSort(int *order)` 函数中，首先计算所有顶点的入度（入边的数量），存储在数组 `InDegree` 中。然后，找到入度为零的顶点作为起点，将它们按顺序放入结果数组 `order` 中，并更新其他顶点的入度。如果在过程中发现有顶点的入度无法减至零，说明图中存在环路，程序会输出错误信息。 5. **代码实现细节**： - `CalInDegree()` 函数用于计算所有顶点的入度，通过遍历每条边并累加到相应顶点的入度计数器。 - 在 `TopoSort()` 中，`top` 变量用于跟踪当前可以添加到排序序列的顶点，`InDegree[top]` 更新为下一个可添加的顶点。 - `MGraph` 类的扩展 `ExtMGraph` 未在提供的代码段中完全展示，但它应该包含类似的图操作，可能针对多对多的关系进行优化。 总结来说，这段代码提供了图数据结构的实现，包括边的表示、图的遍历（DFS 和 BFS）以及拓扑排序等基本运算，这些都是图算法中常用的操作。通过这些基础，我们可以进一步实现更复杂的图算法，如最短路径、最小生成树等。