# BFS/DFS/TopSort | C++

## rlbishop99

### April 29th, 2021 11:42:14 PM

```					#include <bits/stdc++.h>
#define MAXSIZE 50000
#define INF 100000

using namespace std;

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 = 0; //assign the distance of source as 0
visited = 1; //marking as visited

while(!q.empty())
{
u = q.front();
q.pop();

{

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++)
{

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)) //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)
{
}
}

N++; //calculate the number of vertices
}

//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.
}

}

}
```