C++实现：有向图的深度优先与广度优先遍历

"这篇资源是关于有向图的编程实现，包括如何创建有向图以及两种遍历算法：深度优先遍历（Depth First Traversal）和广度优先遍历（Breadth First Traversal）。作者为binfeihan，创建时间为2011年8月15日。" 在计算机科学中，图是一种数据结构，用于表示对象之间的关系或连接。有向图（Directed Graph）是一种特殊的图，其中的边具有方向性，即从一个顶点指向另一个顶点。这与无向图不同，在无向图中，边没有明确的方向。 **创建有向图** 创建有向图通常涉及定义顶点和边。在给定的代码中，`MyGraph` 类模板被用来表示图。它可能包含一个内部数据结构，如邻接列表（Adjacency List），用于存储每个顶点的相邻顶点。邻接列表是一个数组或列表，其中每个元素对应图中的一个顶点，并且包含指向其相邻顶点的引用或指针。 ```cpp // 创建一个简单的有向图类 template <class vType, int size> class MyGraph { private: // 数据结构存储图的信息 public: // 构造函数，初始化图 MyGraph() {} // 添加顶点 void addVertex(vType vertex); // 添加有向边 void addEdge(vType from, vType to); // 邻接顶点获取 void getAdjacentVertices(vType vertex, std::vector<vType>& adjacencyList); // 深度优先遍历 void depthFirstTraversal(vType start); // 广度优先遍历 void breadthFirstTraversal(vType start); }; ``` **深度优先遍历(DFS)** 深度优先遍历是从给定的起始顶点出发，尽可能深地搜索图的分支。在到达一个没有未访问过的相邻顶点时，回溯到上一个顶点，继续探索其他分支。DFS 通常使用递归实现，也可以使用栈来保存待访问的顶点。 在 `MyGraph` 类中，`depthFirstTraversal` 函数会按照以下步骤进行： 1. 从起始顶点开始，将其标记为已访问。 2. 探索所有未访问的相邻顶点，将它们加入待处理队列。 3. 对每个相邻顶点执行相同的过程，直到所有可达顶点都被访问过。 4. 回溯到父顶点，重复步骤2，直到所有顶点都被访问过。 **广度优先遍历(BFS)** 广度优先遍历是从起始顶点开始，逐层遍历所有顶点。首先访问所有与起始顶点直接相连的顶点，然后是这些顶点的相邻顶点，以此类推。BFS 常常使用队列来存储待访问的顶点。 `MyGraph` 类中的 `breadthFirstTraversal` 函数可能会包含以下步骤： 1. 将起始顶点入队，并标记为已访问。 2. 当队列不为空时，取出队首顶点，访问它。 3. 将该顶点的所有未访问的相邻顶点入队，并标记为已访问。 4. 重复步骤2和3，直到队列为空。 深度优先遍历和广度优先遍历各有优势，适用于不同的场景。DFS 适合寻找最短路径（例如，从源顶点到目标顶点的逆向路径），而 BFS 适合找到两个顶点之间的最短路径。在实际应用中，理解这两种遍历方法并能灵活运用是非常重要的。