以下是使用C++编写的图的深度优先搜索遍历算法的示例代码:
#include <iostream>
#include <vector>
using namespace std;
// 图的邻接表表示
class Graph {
private:
int V; // 顶点数
vector<vector<int>> adjList; // 邻接表
public:
Graph(int vertices) {
V = vertices;
adjList.resize(V);
}
void addEdge(int src, int dest) {
adjList[src].push_back(dest);
}
void DFSUtil(int v, vector<bool>& visited) {
visited[v] = true;
cout << "visit vertex: " << v << endl;
for (int i : adjList[v]) {
if (!visited[i]) {
DFSUtil(i, visited);
}
}
}
void DFS() {
vector<bool> visited(V, false);
cout << "深度优先遍历:" << endl;
for (int v = 0; v < V; ++v) {
if (!visited[v]) {
DFSUtil(v, visited);
}
}
}
};
int main() {
int V, E;
cout << "请输入顶点数和边数(输入格式为:顶点数 边数):" << endl;
cin >> V >> E;
Graph graph(V);
cout << "请输入顶点信息(输入格式为:顶点号<CR>),每个顶点以回车作为结束:" << endl;
for (int i = 0; i < V; ++i) {
int vertex;
cin >> vertex;
}
cout << "请输入边的信息(输入格式为:i j):" << endl;
for (int i = 0; i < E; ++i) {
int src, dest;
cin >> src >> dest;
graph.addEdge(src, dest);
}
cout << "邻接表:" << endl;
for (int v = 0; v < V; ++v) {
cout << "vertex " << v << " → ";
for (int i : graph.adjList[v]) {
cout << i << " ";
}
cout << endl;
}
graph.DFS();
return 0;
}
你可以使用以上代码编译运行,然后按照题目要求输入顶点数、边数以及具体的顶点和边信息。最终会输出深度优先遍历结果以及图的邻接表表示。
内容由零声教学AI助手提供,问题来源于学员提问