写一个完整代码,内容是用邻接表表示法,构造无向网G;并从任意一个顶点出发,递归地深度优先遍历该图G
时间: 2024-03-13 11:47:12 浏览: 19
好的,以下是一个使用邻接表表示法构造无向网G,并从任意一个顶点出发递归地深度优先遍历该图的完整代码。
```c++
#include <iostream>
#include <vector>
using namespace std;
// 定义边结构体
struct Edge {
int dest; // 目标顶点
int weight; // 边的权值
Edge(int d, int w): dest(d), weight(w) {}
};
// 定义邻接表节点结构体
struct Node {
int vertex; // 顶点编号
vector<Edge> edges; // 与该顶点相连的边
Node(int v): vertex(v) {}
};
// 邻接表表示法构造无向网G
vector<Node> buildGraph() {
vector<Node> graph;
int numNodes, numEdges;
cout << "请输入顶点数和边数:";
cin >> numNodes >> numEdges;
graph.resize(numNodes);
cout << "请输入每条边的起点、终点和权值:" << endl;
for (int i = 0; i < numEdges; ++i) {
int start, dest, weight;
cin >> start >> dest >> weight;
graph[start].edges.emplace_back(dest, weight);
graph[dest].edges.emplace_back(start, weight);
}
return graph;
}
// 递归地深度优先遍历该图G
void dfs(vector<Node>& graph, vector<bool>& visited, int current) {
visited[current] = true;
cout << current << " ";
for (Edge& e : graph[current].edges) {
int next = e.dest;
if (!visited[next]) {
dfs(graph, visited, next);
}
}
}
int main() {
vector<Node> graph = buildGraph();
vector<bool> visited(graph.size(), false);
int start;
cout << "请输入起始顶点编号:";
cin >> start;
dfs(graph, visited, start);
cout << endl;
return 0;
}
```
运行程序后,根据提示输入顶点数、边数以及每条边的起点、终点和权值。然后输入起始顶点编号,程序就会从该顶点开始递归地深度优先遍历整个图,并输出遍历结果。
阅读全文