DFS 找到的路有多长

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

bfs_path 已经写好。补全 dfs_path：钻到底，找到 t 就一路返回 true，没找到要把自己从 path 里弹出来。把两条路的边数拼起来输出（DFS 在前）。

本节的图：七个点，边 0-1、0-2、1-3、2-4、3-4、5-6；邻接表 G 里每个点的邻居按编号从小到大排。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 把这条最短路径还原出来网格图里的边是什么 →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

vector<vector<int>> G = {{1, 2}, {0, 3}, {0, 4}, {1, 4}, {2, 3}, {6}, {5}};

vector<int> bfs_path(const vector<vector<int>>& g, int s, int t) {
    vector<int> par(g.size(), -2);
    queue<int> q;
    par[s] = -1;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) {
            if (par[v] == -2) {
                par[v] = u;
                q.push(v);
            }
        }
    }
    if (par[t] == -2) return {};
    vector<int> path;
    for (int x = t; x != -1; x = par[x]) path.push_back(x);
    reverse(path.begin(), path.end());
    return path;
}

bool dfs_path(const vector<vector<int>>& g, int u, int t, vector<bool>& seen, vector<int>& path) {
    // TODO: 标记 u、放进 path；到了 t 就返回 true；
    //       否则对没走过的邻居递归，有一个返回 true 就返回 true；都不行就把 u 弹出 path、返回 false
    return false;
}

int main() {
    vector<bool> seen(G.size(), false);
    vector<int> p1;
    dfs_path(G, 0, 4, seen, p1);
    vector<int> p2 = bfs_path(G, 0, 4);
    cout << (int)p1.size() - 1 << "/" << (int)p2.size() - 1 << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

DFS 找到的路有多长

更多题目

全部评论