使用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

下面是一个使用 C++ 实现深度优先搜索的程序：

#include <iostream>
#include <string>
#include <vector>
#include <map>

using namespace std;

// 城市节点
struct CityNode {
    string name;        // 城市名称
    vector<string> adj; // 相邻城市
};

// 城市图
class CityGraph {
public:
    void addCity(const string& name);           // 添加城市节点
    void addEdge(const string& from, const string& to); // 添加城市间的边
    void dfs(const string& from, const string& to);     // 深度优先搜索
private:
    map<string, CityNode> nodes; // 城市节点
    map<string, bool> visited;   // 记录节点是否已经访问过
    bool found;                  // 是否找到目标节点
    vector<string> path;         // 记录路径
};

// 添加城市节点
void CityGraph::addCity(const string& name) {
    if (nodes.find(name) == nodes.end()) {
        CityNode node = {name, vector<string>()};
        nodes[name] = node;
    }
}

// 添加城市间的边
void CityGraph::addEdge(const string& from, const string& to) {
    addCity(from);
    addCity(to);
    nodes[from].adj.push_back(to);
    nodes[to].adj.push_back(from);
}

// 深度优先搜索
void CityGraph::dfs(const string& from, const string& to) {
    found = false;
    path.clear();
    visited.clear();
    for (auto& pair : nodes) {
        visited[pair.first] = false;
    }
    path.push_back(from);
    visited[from] = true;
    if (from == to) { // 如果起点等于终点，直接返回
        found = true;
        return;
    }
    for (const auto& adj : nodes[from].adj) { // 深度优先搜索
        if (!visited[adj]) {
            path.push_back(adj);
            visited[adj] = true;
            if (adj == to) {
                found = true;
                return;
            } else {
                dfs(adj, to);
                if (found) {
                    return;
                } else {
                    path.pop_back();
                    visited[adj] = false;
                }
            }
        }
    }
}

int main() {
    CityGraph graph;
    graph.addEdge("New York", "Chicago");
    graph.addEdge("Chicago", "Denver");
    graph.addEdge("Denver", "Los Angeles");
    string from, to;
    cout << "From? ";
    getline(cin, from);
    cout << "To? ";
    getline(cin, to);
    graph.dfs(from, to);
    if (graph.found) {
        cout << from;
        for (const auto& city : graph.path) {
            cout << " to " << city;
        }
        cout << " Distance is " << (graph.path.size() - 1) * 900 << endl;
    } else {
        cout << "No path found." << endl;
    }
    return 0;
}

在这个程序中，我们定义了一个 CityNode 结构体来表示城市节点，其中包含了城市的名称和相邻城市。然后，我们定义了一个 CityGraph 类来表示城市图，具有添加城市和添加边的功能，以及深度优先搜索的功能。

在深度优先搜索中，我们使用了一个 visited map 来记录每个节点是否已经被访问过，以及一个 path vector 来记录搜索路径。我们从起点开始搜索，如果找到目标节点，就将 found 标志设置为 true 并返回。如果没有找到目标节点，就回溯到上一个节点，继续搜索其它相邻节点，直到遍历完整个图或者找到目标节点为止。

在 main 函数中，我们创建了一个 CityGraph 对象，并且调用了它的 dfs 函数来搜索从起点到终点的路径。如果找到了路径，就输出路径和距离；否则，输出“没有找到路径”的提示。