c++ - 使用 dfs 和 bfs 寻找路径

Question

我的无向图是这样的:-

{0,1,1,0,0,  
 1,0,0,1,0,  
 1,0,0,1,0,  
 0,1,1,0,1,  
 0,0,0,1,0};  

我想使用 bfs 和 dfs 作为我的任务找到两个节点之间的路径。
当我执行 bfs 时，我只是打印应该是最小路径的节点，但它显示 01234，但我想要的是 0134 或 0234，当我执行 dfs 时，它给出 01324。
我的 bfs 代码:-

#include <iostream>
#include<queue>

using namespace std;

int main(){
int matrix[5][5]={0,1,1,0,0,
                  1,0,0,1,0,
                  1,0,0,1,0,
                  0,1,1,0,1,
                  0,0,0,1,0};



//int nodes[3] = {5,6,7};
int visited[5] = {0,0,0,0,0};
int inNode,pathNode;
cout<<"Enter Initial Node: ";
cin>>inNode;
cout<<"Enter Path Node: ";
cin>>pathNode;
int traceBack[5],rec=0;
queue<int> myqueue;
myqueue.push(inNode);
int node = myqueue.front();
visited[inNode] = 1;
//cout<<node<<"\n";


while(!myqueue.empty()){
    int s = myqueue.front();
    myqueue.pop();

    for(int i =0 ; i<5;i++){
        if(matrix[s][i] == 1 && visited[i] == 0){
            myqueue.push(i);
            visited[i] = 1;
            traceBack[rec] = i;
            rec++;
        }

    }
}
    cout<<inNode;
    int j = 0;
    while(traceBack[j]!=pathNode){
        cout<<"->"<<traceBack[j];
        j++;
    }
    cout<<"->"<<pathNode;
return 0;

}

我的 dfs 代码:-

#include<iostream>

using namespace std;

int visited[5]= {0,0,0,0,0};
int traceBack[5],rec=0;
int matrix[5][5]={0,1,1,0,0,
                      1,0,0,1,0,
                      1,0,0,1,0,
                      0,1,1,0,1,
                      0,0,0,1,0};

void dfs(int v){
    int i;
    visited[v]=1;
    for(i= 0 ; i<5;i++){
        if(matrix[v][i] && visited[i]==0){
            traceBack[rec] = i;
            rec++;
            cout<<i;
            dfs(i);
        }
    }
}
int main(){
    int inNode,pathNode;
    cout<<"Enter Initial Node: ";
    cin>>inNode;
    cout<<"Enter Path Node: ";
    cin>>pathNode;
    dfs(inNode);
    int k=0;
    while(traceBack[k]!=pathNode)
    {
        k++;
        cout<<traceBack[k];
    }
    return 0;
}

Answer 1

问题是“traceBack”实际上并没有追溯。它只包含访问节点的顺序，这不一定是您想要的路径。

你需要做什么？

当某个节点s访问另一个节点i时，则traceBack[i] = s。为什么？因为它说我是从 s 访问的，这样每个节点都可以跟踪它的回溯。 (你还初始化了 traceBack[inNode] = -1 因为这个节点没有被任何人访问过)

现在，算法完成后，以下代码将为您提供路径。 (先倒序获取路径，然后倒序得到正确的顺序)

int i = pathNode;

int path[1000];
int path_len = 0;

//this gives you the path in reverse order
while(traceBack[i] != -1){ // there is something to trace
    path[path_len++] = i;   
    i = traceBack[i];
}
path[path_len++] = inNode; // the inNode is left out in the while loop

//printing the path in right order
for(int j = path_len - 1; j >= 0; j—-){
    cout << path[j] << " -> ";
}