Pfad mit dfs und bfs finden

Question

mein ungerichteten Graphen ist dies: -

{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}; 

ich will den Weg zwischen zwei Knoten finden bfs und dfs als meine Aufgabe verwenden.
wenn ich bfs ausführen drucke ich einfach die Knoten, die Mindest-Pfad sein sollte, aber es zeigt,, aber ich möchte 0134 oder 0234 ist und wenn ich dfs ausführen gibt es 01324.
mein bfs Code: -

#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; 

} 

mein dfs Code: -

#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

Sie Problem ist, für BFS, können Sie nicht die gleiche Methode verwenden, wie Sie für DFS verwenden, um zurückverfolgen. Sie können Ihren Code wie folgt ändern:

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[i] = s; 
     } 

    } 
} 

So, jetzt, traceBack enthält die Eltern jedes Knotens. Um den Pfad von Knoten 4 nach 0 zu finden:

Answer 2

Das Problem ist, dass das "traceBack" nicht tatsächlich zurück verfolgt. Es enthält nur die Reihenfolge, in der Knoten besucht wurden, was nicht unbedingt der gewünschte Pfad ist.

Was müssen Sie tun?

Wenn einige Knoten auf einen anderen Knoten i zugreifen, dann traceBack [i] = s. Warum? weil es sagt, dass ich von s zugegriffen wurde, auf diese Weise kann jeder Knoten seine Spur zurück folgen. (Sie initialisieren auch traceBack [inNode] = -1, da auf diesen Knoten von niemandem zugegriffen wurde)

Jetzt, wenn der Algorithmus fertig ist, wird der folgende Code Ihnen den Pfad geben. (Es erhält zuerst den Pfad in umgekehrter Reihenfolge und kehrt es dann um, um die richtige Reihenfolge zu erhalten)

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] << " -> "; 
}