定向圖鄰接矩陣尋找路徑

Question

我想使用BFS方法搜索我的圖，然後確定是否有我的兩個節點之間的路徑。我理解它，並且可以通過鏈表實現它，但是我只是無法用矩陣來理解它。

我相信我在我的循環部分出錯了，我覺得我正在迭代錯誤的東西，或者可能比較錯誤的值。謝謝你的幫助。

這裏是我的代碼：

#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

這將是更好地與NULL

然後初始化AdjMatrix [i] [j]，你可以做

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

你應該重複這種方式

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

，並檢查是否

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

推新頂點到隊列中。