题目描述

基于dfs，求图中a结点到b结点的路径

样例

6 6
1 2
1 3
1 4
2 3
3 4
2 6
1 6

思路1

退出递归时输出 对应 树的后序遍历

C++ 代码

#include<bits/stdc++.h>
using namespace std;
vector<int> res;
const int N = 1e5 + 10;
bool st[N];
int n, m;
int a, b;
struct Node
{
    int id;
    Node* next;
    Node(int _id): id(_id), next(nullptr) {}
}*head[N];             //注意语法

void add(int a, int b)
{
    Node* p = new Node(b);
    p->next = head[a];      //头插法
    head[a] = p;
}

bool dfs(int u)     //是否能找到由a到b的路径；
{
    st[u] = true;             //配合剪枝
    if(u == b)
    {
        cout << u << ' ' << "找到了";
        return true;
    }

    for(Node* p = head[u]; p; p = p->next)
    {
        int j = p->id;
        if(st[j] == false)        //剪枝
        {
            if(dfs(j))
            {
                cout << "退出递归时输出" << u << ' ';
                return true;
            }
        }
    }
    return false;
}
int main()
{
    cin >> n >> m;
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    cin >> a >> b;
    dfs(a);

    return 0;
}

输出

6 找到了退出递归时输出2 退出递归时输出1 

思路2

传统深搜，用path[N]记录入栈的节点；

C++ 代码

bool dfs(int u)     //是否能找到由a到b的路径；
{
    st[u] = true;             //配合剪枝
    path.push_back(u);
    if(u == b)
    {
        return true;
    }

    for(Node* p = head[u]; p; p = p->next)
    {
        int j = p->id;
        if(st[j] == false)        //剪枝
        {
            if(dfs(j))
            {
                return true;
            }
        }
    }
    path.pop_back();
    return false;
}
int main()
{
    cin >> n >> m;
    while(m--)
    {
        int x, y;
        cin >> x >> y;
        add(x, y);
    }
    cin >> a >> b;
    if(dfs(a))
    {
        for(int i = 0; i < path.size(); i ++) cout << path[i] << ' ';
    }

    return 0;
}

输出

1 2 6