用c++编写代码 深度优先搜索判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)

在C++中，我们可以使用深度优先搜索（Depth First Search，DFS）算法来判断邻接表表示的有向图中是否存在从顶点vi到顶点vj的路径。这里是一个简单的示例：

#include <iostream>
#include <vector>
using namespace std;

// 图的邻接表表示
struct Node {
    int destination;
    vector<Node*> adj; // 存储相邻节点的指针
};

// DFS 辅助函数，用于标记访问过的节点并查找路径
bool dfs(Node* node, int target, vector<bool>& visited, vector<int>& path) {
    if (node == nullptr || node->destination == target) { // 到达目标或已到达终点
        path.push_back(target);
        return true;
    }

    visited[node->destination] = true; // 标记已访问

    for (Node* neighbor : node->adj) {
        if (!visited[neighbor->destination] && dfs(neighbor, target, visited, path)) {
            path.push_back(target); // 如果找到路径，则将目标加到路径上
            return true;
        }
    }

    visited[node->destination] = false; // 没找到路径，恢复标记
    path.pop_back(); // 清除最后一步

    return false;
}

// 主函数判断图中是否存在路径
bool hasPath(Node* start, int vi, int vj) {
    vector<bool> visited(start->adj.size(), false);
    vector<int> path;
    return dfs(start, vi, visited, path) && path.back() == vj;
}

int main() {
    // 创建图的邻接列表，这里仅做简化示例
    Node* graph[] = { /* ... */ }; // 实际代码需要填充邻接表节点
    Node* vi_node = find(graph, graph + num_nodes, vi);
    Node* vj_node = find(graph, graph + num_nodes, vj);

    bool result = hasPath(vi_node, vi, vj);
    if (result)
        cout << "存在从" << vi << "到" << vj << "的路径" << endl;
    else
        cout << "不存在从" << vi << "到" << vj << "的路径" << endl;

    return 0;
}

在这个例子中，`hasPath`函数会返回true如果找到了从vi到vj的路径，false则表明无路径。注意这个代码只是一个基本的示例，实际应用中你需要处理图的创建、输入以及节点的查找等细节。