Матрица смежности направленного графа Поиск пути

Я пытаюсь использовать метод 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;
}

0

Решение

Было бы лучше инициализировать AdjMatrix [i] [j] с NULL

Тогда вы можете сделать

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);
}
}
0

Другие решения

Вы должны перебрать этот путь

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

и проверьте,

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

выдвинуть новые вершины в очередь.

0

По вопросам рекламы [email protected]