rendered paste body// ===== main.cpp =====//#include "header dfs.h"#include "header bfs.h"int main(){ int target; graphSearch G; cout << "Input target: " ; cin >> target; G.buildGraph(); G.search(target); cout << endl; return 0; }// ===== header bfs.h =====#ifndef HEADER_BFS_H#define HEADER_BFS_H#include <iostream>#include <vector>#include <queue>#include <windows.h>using namespace std;class node{public: node(){ data = -1; next = NULL; } node(int n){ data = n; next = NULL; } node(int n, node *ptr){ data = n; next = ptr; } void setNode(int n){ data = n; } int getNode() const{ return data; } node* getNext() const{ return next; }private: int data; node* next;}; // [|=== SPACER ===|]class graphSearch{ public: graphSearch(){ visitedList.resize(0); adj.resize(0); searchList.empty(); searchList.push(0); } void buildGraph(){ cout << endl << "Now building a graph for Breadth First Search."; int edgeQty, source, sink; cout << endl << "How many nodes? "; cin >> numNodes; visitedList.resize(numNodes); adj.resize(numNodes); for(int cntra = 0; cntra < numNodes; cntra++){ adj[cntra].resize(0); } cout << endl << "How many edges? "; cin >> edgeQty; cout << endl; for(int cntrb = 1; cntrb <= edgeQty; cntrb++){ cout << "Enter edge set #" << cntrb << " in the format # # :" << endl; cin >> source >> sink; adj[source].push_back(node(sink)); adj[sink].push_back(node(source)); } // Here lies the display of the adjacency array cout << endl; for(int tllya = 0; tllya < int(adj.size()); tllya++){ SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED); cout << tllya; SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY); cout << " | "; SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_GREEN); for(int tllyb = 0; tllyb < int(adj[tllya].size()); tllyb++){ cout << adj[tllya][tllyb].getNode() << " "; } SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY); cout << endl; } } void search(const int target){ int currNodeToCheck = searchList.front(); // .front() in queue, .top() in stack searchList.pop(); if(!visitedList[currNodeToCheck]){ visitedList[currNodeToCheck] = 1; if(currNodeToCheck == target){ cout << endl << "---Found node at " << currNodeToCheck << "!" << endl; system("pause"); exit(0); } cout << endl << "Visiting node #" << currNodeToCheck; for(int k = 0; k < int(adj[currNodeToCheck].size()); k++){ //if(!visitedList[adj[currNodeToCheck][k].getNode()]) searchList.push(adj[currNodeToCheck][k].getNode()); } search(target); } else{ cout << endl << "Ignoring node #" << currNodeToCheck; search(target); } }private: vector <bool> visitedList; vector <vector <node> > adj; queue <int> searchList; int numNodes;};#endif// ===== header dfs.h =====#ifndef HEADER_DFS_H#define HEADER_DFS_H#include <iostream>#include <vector>#include <stack>#include <windows.h>using namespace std;class node{public: node(){ data = -1; next = NULL; } node(int n){ data = n; next = NULL; } node(int n, node *ptr){ data = n; next = ptr; } void setNode(int n){ data = n; } int getNode() const{ return data; } node* getNext() const{ return next; }private: int data; node* next;}; // [|=== SPACER ===|]class graphSearch{ public: graphSearch(){ visitedList.resize(0); adj.resize(0); searchList.empty(); searchList.push(0); } void buildGraph(){ cout << endl << "Now building a graph for Depth First Search."; int edgeQty, source, sink; cout << endl << "How many nodes? "; cin >> numNodes; visitedList.resize(numNodes); adj.resize(numNodes); for(int cntra = 0; cntra < numNodes; cntra++){ adj[cntra].resize(0); } cout << endl << "How many edges? "; cin >> edgeQty; cout << endl; for(int cntrb = 1; cntrb <= edgeQty; cntrb++){ cout << "Enter edge set #" << cntrb << " in the format # # :" << endl; cin >> source >> sink; adj[source].push_back(node(sink)); adj[sink].push_back(node(source)); } // Here lies the display of the adjacency array cout << endl; for(int tllya = 0; tllya < int(adj.size()); tllya++){ SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_RED); cout << tllya; SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY); cout << " | "; SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_GREEN); for(int tllyb = 0; tllyb < int(adj[tllya].size()); tllyb++){ cout << adj[tllya][tllyb].getNode() << " "; } SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), FOREGROUND_INTENSITY); cout << endl; } } void search(const int target){ int currNodeToCheck = searchList.top(); // .front() in queue, .top() in stack searchList.pop(); if(!visitedList[currNodeToCheck]){ visitedList[currNodeToCheck] = 1; if(currNodeToCheck == target){ cout << endl << "---Found node at " << currNodeToCheck << "!" << endl; system("pause"); exit(0); } cout << endl << "Visiting node #" << currNodeToCheck; for(int k = 0; k < int(adj[currNodeToCheck].size()); k++){ //if(!visitedList[adj[currNodeToCheck][k].getNode()]) searchList.push(adj[currNodeToCheck][k].getNode()); } search(target); } else{ cout << endl << "Ignoring node #" << currNodeToCheck; search(target); } }private: vector <bool> visitedList; vector <vector <node> > adj; stack <int> searchList; int numNodes;};#endif