bfs

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N=100010;

int pre[N];
int q[N];
bool st[N];
int n,m;

struct Node{
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL){}
}*head[N];

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

void bfs(int u,int v){
    int hh=0,tt=-1;
    q[++tt]=u;
    st[u]=true;
    pre[u]=-1;

    while(hh<=tt){
        int t=q[hh++];

        if(t==v){
            printf("存在%d到%d的路径\n",u,v);

            vector<int> a;
            for(int i=t;i!=-1;i=pre[i])
                a.push_back(i);
            reverse(a.begin(),a.end());

            for(int i=0;i<a.size();i++)
                cout<<a[i]<<' ';

            return ;
        }

        for(auto p=head[t];p;p=p->next){
            int j=p->id;
            if(!st[j]){
                q[++tt]=j;
                st[j]=true;
                pre[j]=t;
            }
        }
    }

    printf("不存在%d到%d的路径",u,v);
}

int main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    bfs(1,5);

    return 0;
}

dfs(退出递归时输出，对应树的后序遍历)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=100010;

bool st[N];
int n,m;

struct Node{
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL){}
}*head[N];

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

bool dfs(int u,int v){
    st[u]=true;

    if(u==v){
        cout<<v;
        return true;
    }

    for(auto p=head[u];p;p=p->next){
        int j=p->id;
        if(!st[j]){
            if(dfs(j,v)){
                cout<<' '<<u;
                return true;
            }
        }
    }
    return false;
}

int main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    if(!dfs(1,5)) 
        printf("不存在1到5的路径");

    return 0;
}

dfs(全排列回溯，对应树的先序遍历)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N=100010;

vector<int> a;
bool st[N];
int n,m;

struct Node{
    int id;
    Node* next;
    Node(int _id):id(_id),next(NULL){}
}*head[N];

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

bool dfs(int u,int v){
    st[u]=true;
    a.push_back(u);

    if(u==v){
        printf("存在路径\n");
        for(int i=0;i<a.size();i++)
            cout<<a[i]<<' ';
        cout<<endl;

        return true;
    }

    for(auto p=head[u];p;p=p->next){
        int j=p->id;
        if(!st[j]){
            if(dfs(j,v))
                return true;
        }
    }

    a.pop_back();
    return false;
}

int main(){
    cin>>n>>m;
    while(m--){
        int a,b;
        cin>>a>>b;
        add(a,b);
    }

    if(!dfs(1,6)) 
        printf("不存在1到6的路径");

    return 0;
}