有向图邻接矩阵求路径

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

将新顶点推入队列。

有向图邻接矩阵求路径

Directed Graph Adjacency Matrix Finding the Path

c++

loops

graph

breadth-first-search

adjacency-matrix