BFS/DFS/TopSort | C++

April 29th, 2021 11:42:14 PM

					
#include <bits/stdc++.h> #define MAXSIZE 50000 #define INF 100000 using namespace std; vector<int> adj[MAXSIZE]; //Adjacency List bool visited[MAXSIZE]; //Checks if a node is visited or not in BFS and DFS bool isConnected = true; //Checks if the input graph is connected or not int dist[MAXSIZE], discover[MAXSIZE], finish[MAXSIZE]; //Distance for BFS, in time and out time for DFS int t = 1; //Time used for DFS int u, v, i, j, k, N = 0; stack<int> st; //Stack for TopSort multiset<pair<int, int>> s; //collection of pairs to sort by distance pair<int, int> current; //pointer variable to a position in the multiset void BFS() { queue<int> q; //queue for BFS q.push(1); //pushing the source dist[1] = 0; //assign the distance of source as 0 visited[1] = 1; //marking as visited while(!q.empty()) { u = q.front(); q.pop(); for(i=0; i < adj[u].size(); i++) { v = adj[u][i]; //Adjacent vertex if(!visited[v]) //if not visited, update the distance and push onto queue { visited[v] = 1; dist[v] = dist[u]+1; q.push(v); } } } for(i = 1; i <= N; i++) { s.insert(make_pair(dist[i], i)); //for sorted distance } cout << "BFS results:" << endl; //prints BFS results and checks if the graph is connected while(!s.empty()) { current = *s.begin(); s.erase(s.begin()); i = current.second; j = current.first; if(j == INF) //if any infinite value, graph is not connected { cout << i << " INF" << endl; isConnected = false; } else { cout << i << " " << j << endl; } } //marks blocks of memory as visited memset(visited, 0, sizeof visited); } void dfsSearch(int s) { visited[s] = 1; //marking it visited discover[s] = t++; //assigning and incrementing time int i, v; for(i = 0; i < adj[s].size(); i++) { v = adj[s][i]; if(!visited[v]) //if vertex is not visited then visit, else continue { dfsSearch(v); } } st.push(s); //pushed onto stack for TopSort if it was called finish[s] = t++; //out time } void DFS() { for(i = 1; i <= N; i++) { if(visited[i]) //if visited continue, else visit it with DFS { continue; } dfsSearch(i); //embedded function to actually perform DFS } for(i=1;i<=N;i++) { s.insert(make_pair(discover[i], i)); //minheap for sorted discovery time } cout << "DFS results:" << endl; while(!s.empty()) //Prints DFS results as long as the multiset is not empty { current = *s.begin(); //duplicates the pointer to first object in the multiset s.erase(s.begin()); //erases the first object in multiset i = current.second; cout << i << " " << discover[i] << " " << finish[i] << endl; //prints discover times and finish times } } void TopSort() { //call DFS so we can have a sorted stack to print for(i=1;i<=N;i++) { if(visited[i]) { continue; } dfsSearch(i); } cout<<"Topological Sort results:"<<endl; //print sorted results from DFS while(!st.empty()) { i = st.top(); st.pop(); cout << i << endl; } //declare blocks of memory as visited memset(visited, 0, sizeof visited); } int main() { string str, num, input; int selection, connectedChoice = 0; //get to input any file, more freedom than declaring file in command line cout << "Enter the exact name of your input file [case sensitive]: "; cin >> input; ifstream inputFile(input); //Read the input file //checks if the ifstream cannot open if(inputFile.fail()) { cout << endl << "No input files matching that name. Terminating..." << endl; return 0; } //Read until the end of file while(!inputFile.eof()) { getline(inputFile, str); //read the current line if(str == "") { continue; } if(!isdigit(str[0])) //checks to see if the first item in a line is a digit or not { cout << "Invalid file format. You have a line beginning with a non-digit. Terminating..." << endl; return 0; } stringstream ss; ss << str; //convert the line to stream of strings ss >> num; //read the line num stringstream(num) >> u; while(!ss.eof()) { ss>>num; if(stringstream(num) >> v) { adj[u].push_back(v); //read the adjacent vertices } } N++; //calculate the number of vertices sort(adj[u].begin(), adj[u].end()); //sort the adjacency list in case it is not sorted } //creates arbitrary values for distance, will check later if INF remain for(i = 1; i <= N; i++) { dist[i] = INF; } cout << endl << "Valid Input file loaded!" << endl; while(selection != 4) { cout << "************************************************" << endl; cout << "What type of analysis would you like to perform?" << endl; cout << "1: Breadth-First Search" << endl; cout << "2: Depth-First Search" << endl; cout << "3: Topological Sort" << endl; cout << "4: Quit" << endl; cout << "************************************************" << endl; //read user input and execute selection cin >> selection; switch(selection) { case 1: cout << endl; BFS(); cout << endl; cout << "Would you like to know if the graph is connected?" << endl; cout << "1: Yes" << endl; cout << "Any other key: No" << endl; cin >> connectedChoice; switch(connectedChoice) { case 1: if(!isConnected) { cout << "The graph is not connected." << endl << endl; } else { cout << "The graph is connected!" << endl << endl; } break; default: break; } break; case 2: cout << endl; DFS(); cout << endl; break; case 3: cout << endl; TopSort(); cout << endl; break; case 4: return 0; default: cout << endl << "Invalid selection." << endl; //loops the selection prompt until a valid selection is input. } } }

Featured Posts