For this assignment you are to create a C++ class that implements a graph using
ID: 3786921 • Letter: F
Question
For this assignment you are to create a C++ class that implements a graph using either an adjacency list or an adjacency matrix. Your class is to implement the following functions
- DFS
- BFS
- DFS Spanning Tree
- BFS Spanning Tree
Each function should take the node to start at as its parameter
Your program will take in 2 files. One called dat.txt and one called cmd.txt. dat.txt contains the list of nodes that are to be added to the graph and cmd.txt contains the commands to be run against your program.
File Format
dat.txt
<number of nodes>
<0 or 1 | directed or undirected>
<source node> <destination node>
Example file
7
1
1 3
1 4
1 2
2 4
2 5
3 4
3 6
4 5
4 6
4 7
5 7
6 7
cmd.txt
<command> <0 or 1 arguments>
Commands
- 1 bfs
- 2 dfs
- 3 bfs spanning
- 4 dfs spanning
Example File
1 1
2 1
3 1
4 1
Expectations
You should not use any already implemented code such as a library for your linked list
Your code should be well formatted with proper spacing and proper naming
Your code should have well named variables. No a’s b’s or c’s as names unless it is for something like a loop counter
Your code should have the same output formatting you see below
DFS Stat 1 1 4 6 3 5 2 HFS Start 1 2 4 5 6 7 DFS Span tree start 1 DITS span tree start 1 K1. 23 1. 3) K1 4X2 5 K3. 6X4.Explanation / Answer
class Program Graph
{
int Z;
list<int> *adjacent_side;
public:
Program Graph(int Z);
void add Side(int v, int w);
void BFS(int s);
void DFS(int s);
};
void Program Graph::BFS(int s)
{
bool *completed = new bool[Z];
for(int i = 0; i < Z; i++)
completed[i] = false;
list<int> linked queue;
completed[s] = true;
linked queue.push_back(s);
list<int>::iterator i;
while(!linked queue.empty())
{
s = linked queue.front();
cout << s << " ";
linked queue.pop_front();
for(i = adjacent_side[s].begin(); i != adjacent_side[s].end(); ++i)
{
if(!completed[*i])
{
completed[*i] = true;
linked queue.push_back(*i);
}
}
}
}
void Program Graph::DFS(int s)
{
bool *completed = new bool[Z];
for(int i = 0; i < Z; i++)
completed[i] = false;
stack<int> linked stack;
completed[s] = true;
linked stack.push(s);
list<int>::iterator i;
while (!linked stack.empty())
{
s = linked stack.top();
cout << s << " ";
linked stack.pop();
for (i = adjacent_side[s].begin(); i != adjacent_side[s].end(); ++i)
{
if (!completed[*i])
{
completed[*i] = true;
linked stack.push(*i);
}
}
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.