I am implementing a graph. I have print, BFS and DFS methods. My print, BFS, and DFS would work normally if I run them separately, however, if I run them one after another one, for example, I ran BFS after print, the BFS won't work. It seems I changed my array in my methods but I did not, can anyone help me with this?
below is my graph.h
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <queue>
using namespace std;
struct node{
char ID;
int WEIGHT;
int DISTANCE;
bool VISITED;
node(char,int);
node *next;
};
struct myGraph{
public:
void addEdge(node* [], char,char,int);
void printGraph(node* [], int V);
void BFS(node* [],char);
void visitedNode(node* [], char head, int);
void DFS(node* [],char);
};
below is my graph.cpp
#include "myGraph.h"
node::node(char id, int weight) {
this->ID = id;
this->WEIGHT = weight;
this->VISITED = false;
this->DISTANCE = 0;
this->next = nullptr;
}
void myGraph::addEdge(node* adj[], char head, char end, int weight)
{ int parent = head - 'a';
node* newNode = new node(head,0);
node* anotherNode = new node(end,weight);
if (adj[parent] == nullptr){
adj[parent] = newNode;
adj[parent]->next = anotherNode;
}
else{
node *temp = adj[parent];
while(temp->next != nullptr){
temp = temp->next;
}
temp->next= anotherNode;
}
}
void myGraph::printGraph(node* adj[], int V)
{
for (int v = 0; v < V; v++)
{
if (adj[v] != nullptr){
cout << "Adjacency list: "<<endl;
cout<<"Head: "<<adj[v]->ID<<" -> ";
while (adj[v]->next != nullptr){
adj[v]= adj[v]->next;
cout <<"Id: "<<adj[v]->ID <<" Weight: "<<adj[v]->WEIGHT<<" -> ";
}
cout<<"nullptr"<<endl;
}
}
}
void myGraph::visitedNode(node* adj[], char target, int size){
for (int i = 0; i < size; i++){
node* temp = adj[i];
while (temp != nullptr){
if (temp->ID == target){
temp->VISITED = true;
}
temp = temp->next;
}
}
}
void myGraph::BFS(node* adj[],char head) {
queue<node*> temp;
vector<node*> result;
node * tempNode = adj[head-'a']; //assign head pointer to tempNode
temp.push(tempNode);
visitedNode(adj,tempNode->ID,9);
while (!temp.empty()){
tempNode = adj[temp.front()->ID - 'a'];
temp.pop();
result.push_back(tempNode);
while(tempNode->next != nullptr){
if (!tempNode->VISITED){
temp.push(tempNode);
visitedNode(adj,tempNode->ID,9);
}
tempNode = tempNode->next;
}
if (!tempNode->VISITED){
temp.push(tempNode);
visitedNode(adj,tempNode->ID,9);
}
}
cout<<"Traverse by BFS: "<<endl;
for (auto i : result){
cout<<i->ID <<" ";
}
}
void myGraph::DFS(node* adj[],char head){
stack<node*> temp;
vector<node*> result;
node * tempNode = adj[head-'a'];
temp.push(tempNode);
visitedNode(adj,tempNode->ID,9);
while(!temp.empty()){
while (tempNode->next != nullptr){
if (!tempNode->next->VISITED){
tempNode = adj[tempNode->next->ID - 'a'];
visitedNode(adj,tempNode->ID,9);
temp.push(tempNode);
}
else{
tempNode = tempNode->next;
}
}
result.push_back(temp.top());
temp.pop();
if (!temp.empty()){
tempNode = temp.top();
}
}
cout<<"Traverse by DFS: "<<endl;
for (auto i : result){
cout<<i->ID <<" ";
}
}
below is my main
#include "main.h"
int main() {
myGraph *tryme = new myGraph();
const int V = 9;
node* adj[V] = {};
tryme->addEdge(adj, 'a','b',2);
tryme->addEdge(adj, 'a','c',4);
tryme->addEdge(adj, 'a','d',6);
tryme->addEdge(adj, 'b','c',5);
tryme->addEdge(adj, 'b','a',2);
tryme->addEdge(adj, 'c','b',5);
tryme->addEdge(adj, 'c','d',1);
tryme->addEdge(adj, 'c','e',2);
tryme->addEdge(adj, 'c','a',4);
tryme->addEdge(adj, 'd','h',4);
tryme->addEdge(adj, 'd','f',3);
tryme->addEdge(adj, 'd','c',1);
tryme->addEdge(adj, 'd','a',6);
tryme->addEdge(adj, 'e','c',2);
tryme->addEdge(adj, 'e','i',3);
tryme->addEdge(adj, 'e','g',5);
tryme->addEdge(adj, 'e','f',1);
tryme->addEdge(adj, 'f','g',4);
tryme->addEdge(adj, 'f','e',1);
tryme->addEdge(adj, 'f','d',3);
tryme->addEdge(adj, 'g','e',5);
tryme->addEdge(adj, 'g','f',4);
tryme->addEdge(adj, 'h','d',4);
tryme->addEdge(adj, 'i','e',3);
tryme->printGraph(adj, V);
tryme->DFS(adj,'a');
tryme->BFS(adj,'a');
If I only call print, or only call DFS, or only call BFS, the code works fun, if I call them one by one, below is the output
Adjacency list:
Head: a -> Id: b Weight: 2 -> Id: c Weight: 4 -> Id: d Weight: 6 -> nullptr
Adjacency list:
Head: b -> Id: c Weight: 5 -> Id: a Weight: 2 -> nullptr
Adjacency list:
Head: c -> Id: b Weight: 5 -> Id: d Weight: 1 -> Id: e Weight: 2 -> Id: a
Weight: 4 -> nullptr
Adjacency list:
Head: d -> Id: h Weight: 4 -> Id: f Weight: 3 -> Id: c Weight: 1 -> Id: a
Weight: 6 -> nullptr
Adjacency list:
Head: e -> Id: c Weight: 2 -> Id: i Weight: 3 -> Id: g Weight: 5 -> Id: f
Weight: 1 -> nullptr
Adjacency list:
Head: f -> Id: g Weight: 4 -> Id: e Weight: 1 -> Id: d Weight: 3 -> nullptr
Adjacency list:
Head: g -> Id: e Weight: 5 -> Id: f Weight: 4 -> nullptr
Adjacency list:
Head: h -> Id: d Weight: 4 -> nullptr
Adjacency list:
Head: i -> Id: e Weight: 3 -> nullptr
Traverse by DFS:
d Traverse by BFS:
a d