判断两个结点之间是否存在路径，若存在则输出路径

BFS实现

//1、建立pre数组存储每个结点的前驱结点，建立st状态数组与辅助队列来实现BFS；
//2、在BFS过程中，若取出的队头元素与待确定的路径终点元素相等，则说明路径存在；
//3、利用path串起pre数组，得到两个节点间路径并输出。
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 1e5;

int n,m,pre[N];
bool st[N];
int ss = 1, tt = 6;//求结点1到6的路径

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

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

void bfsFindPath(int ss){
    queue<int> q;
    q.push(ss);
    st[ss] = true;
    pre[ss] = -1;

    while(q.size()){
        int t = q.front();
        q.pop();

        if(t == tt){
            cout << "路径存在" << endl;
            vector<int> path;

            for(int i = t ; i != -1; i = pre[i]){
                path.push_back(i);
            }
            reverse(path.begin(), path.end());

            for(int j = 0; j < path.size(); j++){
                cout << path[j] << ' ';
            }

            return;
        }

        for(Node *p = head[t]; p; p = p -> next){
            int u = p -> val;
            if(!st[u]){
                st[u] = true;
                q.push(u);
                pre[u] = t;
            }
        }
    }
    cout << "不存在这样的路径" ;
}

int main(){
    cin >> n >> m;
    int a, b;

    for(int i = 1; i <= m; i++){
        cin >> a >> b;
        add(a,b);
    }

    bfsFindPath(ss);

    return 0;
}

DFS实现1(递归退层时输出结点，对应树的后续遍历)

#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>

using namespace std;

const int N = 1e5;

int n,m;
bool st[N];
int ss = 1, tt = 6;//求结点1到6的路径

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

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

bool dfsFindPath(int u){
    st[u] = true;

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

    for(Node* p = head[u]; p; p = p -> next){
        int t = p -> val;
        if(!st[t]){
            if(dfsFindPath(t)){
                cout << " <- " << u;
                return true;
            }
        }
    }

    return false;

}


int main(){
    cin >> n >> m;
    int a, b;

    for(int i = 1; i <= m; i++){
        cin >> a >> b;
        add(a,b);
    }

    if(!dfsFindPath(ss)) puts("路径不存在");

    return 0;
}

DFS实现2（全排列法寻找路径，对应树的先序遍历）

bool dfsFindPath(int u){
    st[u] = true;
    path.push_back(u);

    if(u == tt){
        cout << "路径存在" << endl;
        for(int i = 0; i < path.size(); i++){
            if(i > 0) cout << " -> ";
            cout << path[i] ;
        }
        return true;
    }

    for(Node* p = head[u]; p; p = p -> next){
        int t = p -> val;
        if(!st[t]){
            if(dfsFindPath(t)){
                return true;//成功找到路径
            }
        }
    }
    path.pop_back();//若该结点不是所求路径中的结点则删去

    return false;

}