c++ - Directed Graph Adjacency Matrix Finding the Path -
i trying use bfs method search through graph , determine if there path between 2 nodes. understand , can implement linked list, having trouble grasping matrix instead.
i believe going wrong in looping section, feel iterating on wrong thing, or maybe comparing wrong values. help.
here code have:
#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 = 0; < 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 = 0; < total_stations; ++){ 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 if same node statement" << endl; return true; } visited[from] = true; verticies.push(from); cout << "testing if there route " << << " " << << endl; while(!verticies.empty() && route == false ){ int current; current = verticies.front(); verticies.pop(); cout << "going loop, current value of " << current << endl; ( int = adjmatrix[current][0]; < total_stations ; i++ ){ if (i == ){ 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 1 2, weight of 10. newgraph.addroute(2,9,1); //route of 2 9, weight of 1. newgraph.printgraph(); bool answer = newgraph.isroute(3,9); //should no route... if (answer){ cout << "there route!" << endl; } else{ cout << "there no route!" << endl; } return 0; }
it better initialize adjmatrix[i][j] null
then can do
for ( int = 0; < total_stations ; i++ ){ if (adjmatrix[current][i]!=null) { if (i == ){ route = true; break; } if ( visited[i] == false){ visited[i] = true; verticies.push(i); } }
Comments
Post a Comment