Directed Graph Adjacency Matrix Den Pfad finden

Question

Ich versuche, die BFS-Methode zu verwenden, um mein Diagramm zu durchsuchen und dann zu bestimmen, ob es einen Pfad zwischen meinen zwei Knoten gibt. Ich verstehe es und kann es mit einer verknüpften Liste implementieren, aber ich habe nur Schwierigkeiten, es mit einer Matrix zu begreifen.

Ich glaube, dass ich in meinem Looping-Bereich falsch liege, ich habe das Gefühl, dass ich das falsche Ding wiederhole oder vielleicht die falschen Werte vergleiche. Danke für jede Hilfe. Hier

ist der Code, den ich habe:

#include <iostream> 
#include <queue> 
#include <string.h> 
#include <stack> 
#include <list> 

using namespace std; 

class Graph{ 
private: 
    int total_routes; 
    int total_stations; 
public: 
    int AdjMatrix[100][100]; 
    Graph(int routes, int stations); 

    void addRoute(int from, int to, int weight); 
    void printGraph(); 
    bool isRoute(int from, int to); 
}; 

Graph::Graph(int routes, int stations) 
{ 
    for(int i = 0; i < stations; i++){ 
     for(int j=0; j < stations; j++){ 
      AdjMatrix[i][j]=0; 
     } 
    } 
    total_routes = routes; 
    total_stations = stations; 
} 

void Graph::printGraph(){ 
    cout << "\n" << endl; 
    for(int i = 0; i < total_stations; i ++){ 
     for(int j = 0; j < total_stations; j++){ 
      cout << " " << AdjMatrix[i][j]; 
     } 
     cout << endl; 
    } 
} 

void Graph::addRoute(int from, int to, int weight){ 
    AdjMatrix[from][to] = weight; 
} 

bool Graph::isRoute(int from, int to){ 
    bool route = false; 

    bool visited[total_stations] = {false}; 

    queue<int> verticies; 

    if (from == to){ 
     cout << "Going into if its the same node statement" << endl; 
     return true; 
    } 

    visited[from] = true; 
    verticies.push(from); 

    cout << "Testing if there is a route from " << from << " To " << to << endl; 
    while(!verticies.empty() && route == false){ 
     int current; 
     current = verticies.front(); 
     verticies.pop(); 
     cout << "Going into for Loop, with a current value of " << current << endl; 
     for (int i = AdjMatrix[current][0]; i < total_stations ; i++){ 
      if (i == to){ 
       route = true; 
       break; 
      } 
      if (visited[i] == false){ 
       visited[i] = true; 
       verticies.push(i); 
      } 
     } 
    } 
    return route; 
} 

int main() { 

    Graph newGraph(2,10);   //10 stations(Nodes), 2 routes 
    newGraph.addRoute(0,1,10);  //Route from 1 to 2, with a weight of 10. 
    newGraph.addRoute(2,9,1);  //Route of 2 to 9, with a weight of 1. 
    newGraph.printGraph(); 
    bool answer = newGraph.isRoute(3,9); //Should say no route... 
    if (answer){ 
     cout << "There is a route!" << endl; 
    } 
    else{ 
     cout << "There is no route!" << endl; 
    } 
    return 0; 
} 

Answer 1

Es wäre besser, AdjMatrix zu initialisieren [i] [j] mit NULL

Dann können Sie

for (int i = 0; i < total_stations ; i++){ 
     if (AdjMatrix[current][i]!=NULL) 
     { 
      if (i == to){ 
       route = true; 
       break; 
      } 
      if (visited[i] == false){ 
       visited[i] = true; 
       verticies.push(i); 
      } 
     } 

Answer 2

tun sollten Sie über diesen Weg iterieren

for (int i = 0; i < total_stations ; i++)

und prüfen, ob

visited[i] == false && AdjMatrix[current][i] != 0

neue Eckpunkte in die Warteschlange zu drücken.