使用c++完成下面设计:(1)深度优先搜索: ①深度优先搜索在尝试另一种路径之前,会探索每条可能的路径,直到结束。 ②算法: 如图3-2所示。深度优先搜索按ABDBEBACF顺序遍历。其中A是起点,F是终点。 深度优先搜索是树的中序遍历。即路径一直向左,直到遇到终端节点或者找到目标。如果达到终端节点,路径回退到上一层,转向右边,然后在向左边搜索,直到遇到目标或者终端节点。这个过程一直持续到发现目标或者检查到搜索空间中的最后一个节点。 ③main()提示您输入出发城市和目标城市。这意味可使用此程序来寻找任何两个城市之间的航线。 下面是运行结果: From? New York To? Los Angeles New York to Chicago to Denver to Los Angeles Distance is 2900 其中纽约到芝加哥900英里,芝加哥到丹佛1000英里,纽约到多伦多500英里,纽约到丹佛1800英里,多伦多
时间: 2024-03-21 19:39:27 浏览: 18
到芝加哥800英里,丹佛到洛杉矶1000英里,共计2900英里。以下是C++代码实现:
```
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <stack>
using namespace std;
map<string, vector<pair<string, int>>> graph; // 存放城市和对应的航线和距离
map<string, bool> visited; // 存放城市是否被访问过
int dfs(string from, string to) {
stack<pair<string, int>> s; // 存放当前访问到的城市和距离
s.push(make_pair(from, 0));
visited[from] = true; // 标记起点已经被访问
while (!s.empty()) {
string curr = s.top().first;
int distance = s.top().second;
s.pop();
if (curr == to) { // 找到目标城市,返回距离
return distance;
}
for (auto& p : graph[curr]) { // 遍历当前城市的航线
string next = p.first;
int next_distance = p.second;
if (!visited[next]) { // 如果下一个城市没有被访问过,入栈
visited[next] = true;
s.push(make_pair(next, distance + next_distance));
}
}
}
return -1; // 没有找到目标城市,返回-1
}
int main() {
// 建立城市和对应的航线和距离
graph["New York"] = {{"Chicago", 900}, {"Toronto", 500}, {"Denver", 1800}};
graph["Chicago"] = {{"New York", 900}, {"Toronto", 400}, {"Denver", 1000}};
graph["Toronto"] = {{"New York", 500}, {"Chicago", 400}};
graph["Denver"] = {{"New York", 1800}, {"Chicago", 1000}, {"Los Angeles", 1000}};
graph["Los Angeles"] = {{"Denver", 1000}};
string from, to;
cout << "From? ";
getline(cin, from);
cout << "To? ";
getline(cin, to);
int distance = dfs(from, to);
if (distance == -1) {
cout << "No route found." << endl;
} else {
cout << from << " to " << to << " Distance is " << distance << endl;
}
return 0;
}
```
注意:此代码仅为示例,实际上应该对输入进行一些错误处理,例如输入的城市不存在,输入的起点和终点相同等等。