已知邻接矩阵，用DFS寻找路径C++

在C++中，使用深度优先搜索（Depth-First Search, DFS）遍历图并查找从起点到终点的路径时，首先需要定义一个邻接矩阵来存储图的关系。邻接矩阵是一个二维数组，其中每个元素表示两个顶点之间是否存在边。

以下是基本的步骤：

1. 定义一个结构体或类来表示节点，包含顶点值和访问标记（例如`bool visited[]`用于记录是否已访问过）。

2. 创建一个布尔型函数`dfs(int vertex, int target)`，接受当前顶点`vertex`和目标顶点`target`作为参数。这个函数将按照深度优先的方式进行搜索，并返回是否存在路径。

bool dfs(int vertex, int target, vector<vector<bool>>& graph, vector<bool>& visited) {
    if (vertex == target) {
        return true; // 找到了目标节点，直接返回true
    }
    
    visited[vertex] = true; // 标记当前节点已访问

    for (int neighbor : graph[vertex]) { // 遍历邻居
        if (!visited[neighbor]) {
            if (dfs(neighbor, target, graph, visited)) { // 递归尝试邻居
                return true;
            }
        }
    }

    visited[vertex] = false; // 如果未找到路径，回溯时还原访问标记
    return false;
}

3. 调用`dfs`函数，传递起始节点、目标节点以及邻接矩阵：

vector<int> path;
path.push_back(start); // 起始路径记录
if (dfs(start, end, adjacencyMatrix, visitedArray)) {
    // 有路径存在，从起始节点开始反向构建路径
    int current = end;
    while (current != start) {
        path.push_back(current);
        current = findAdj(current, start, adjacencyMatrix); // 查找上一步的前驱节点
    }
    reverse(path.begin(), path.end()); // 反转路径顺序
} else {
    cout << "No path found from " << start << " to " << end << endl;
}

其中`findAdj`函数用于查找上一步的前驱节点。