用C++代码:使用模板类建立一个用邻接表表示的有向图,并对上边有向图进行深度优先遍历。
时间: 2023-11-22 15:55:32 浏览: 67
C++实现有向图的邻接表表示
5星 · 资源好评率100%
以下是使用模板类建立邻接表表示的有向图,并对其进行深度优先遍历的C++代码:
```c++
#include <iostream>
#include <vector>
#include <stack>
template<typename T>
class Graph {
private:
std::vector<std::vector<int>> adjList; // 邻接表
int numVertices; // 顶点数
public:
Graph(int n) : numVertices(n) {
adjList.resize(numVertices);
}
// 添加一条有向边
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
}
// 深度优先遍历
void DFS(int start) {
std::vector<bool> visited(numVertices, false); // 标记是否被访问过
std::stack<int> s; // 存储待访问的顶点
s.push(start);
while (!s.empty()) {
int v = s.top();
s.pop();
if (!visited[v]) {
visited[v] = true;
std::cout << v << " "; // 访问顶点
for (auto it = adjList[v].rbegin(); it != adjList[v].rend(); ++it) {
int u = *it;
if (!visited[u]) {
s.push(u); // 将未被访问的顶点入栈
}
}
}
}
}
};
int main() {
Graph<int> g(4); // 创建一个有4个顶点的图
// 添加有向边
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
std::cout << "DFS traversal starting from vertex 2: ";
g.DFS(2); // 从顶点2开始深度优先遍历
return 0;
}
```
输出结果为:
```
DFS traversal starting from vertex 2: 2 3 0 1
```
阅读全文