C++语言编程 无向图判断节点存在路径

Question

创建无向图邻接矩阵G，实现一个函数isPath(v, w)，其中v和w是图中的顶点，检查两个节点之间是否有路径。找到的路径将作为整数序列(节点值)打印到文本文件中。

Answer 1

 #include<bits/stdc++.h>
using namespace std;
int f[1000][1000];
int h[1000];
vector<int>path;
int n,m;
bool pathed=0;
void isPath(int now,int end){
    if(now==end){
        pathed=1;
        return ;
    }
    h[now]=1;
    for(int i=1;i<=n;i++){
        if(f[now][i]&&!h[i]){
            path.push_back(i);
            isPath(i,end);
            if(pathed)return ;
            path.pop_back();
        }
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        f[x][y]=1;
        f[y][x]=1;
    }
    int x,y;
    cin>>x>>y;
    path.push_back(x);
    isPath(x,y);
    if(pathed){
        cout<<path[0];
        for(int i=1;i<path.size();i++){
            cout<<"->"<<path[i];
        }
        cout<<endl;
    }else{
        cout<<"No path between "<<x<<" and "<<y<<" !"<<endl;
    }
    return 0;
}

如有问题，请私聊QQ：3143664703