Data Structures For this assignment you are to create a C++ class that implement
ID: 3681647 • Letter: D
Question
Data Structures
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
Explanation / Answer
Answer:
class ProgramGraph
{
int Z;
list<int> *adjacent_side;
public:
ProgramGraph(int Z);
void addSide(int v, int w);
void BFS(int s);
void DFS(int s);
};
void ProgramGraph::BFS(int s)
{
bool *completed = new bool[Z];
for(int i = 0; i < Z; i++)
completed[i] = false;
list<int> linkedqueue;
completed[s] = true;
linkedqueue.push_back(s);
list<int>::iterator i;
while(!linkedqueue.empty())
{
s = linkedqueue.front();
cout << s << " ";
linkedqueue.pop_front();
for(i = adjacent_side[s].begin(); i != adjacent_side[s].end(); ++i)
{
if(!completed[*i])
{
completed[*i] = true;
linkedqueue.push_back(*i);
}
}
}
}
void ProgramGraph::DFS(int s)
{
bool *completed = new bool[Z];
for(int i = 0; i < Z; i++)
completed[i] = false;
stack<int> linkedstack;
completed[s] = true;
linkedstack.push(s);
list<int>::iterator i;
while (!linkedstack.empty())
{
s = linkedstack.top();
cout << s << " ";
linkedstack.pop();
for (i = adjacent_side[s].begin(); i != adjacent_side[s].end(); ++i)
{
if (!completed[*i])
{
completed[*i] = true;
linkedstack.push(*i);
}
}
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.