Question

You will be implementing a Breadth-First Search (BFS) and a Depth-First Search (DFS) algorithm on a graph stored as an adjacency list. The AdjacencyList class inherits from the Graph class shown below. class Graph { private: vector _distances; vector _previous; public: Graph() { } virtual int vertices() const = 0; virtual int edges() const = 0; virtual int distance(int) const = 0; virtual void bfs(int) const = 0; virtual void dfs(int) const = 0; virtual void display() const = 0; }; It is up to you how you would like to store the data internally, however, the AdjacencyList class must be stored as an adjacency list as discussed in class. The input file is formatted with the first line being the number of vertices in the graph (labelled 0 - N-1) and the rest of the lines being the edges in a directed graph with the first integer being the source vertex and the second vertex being the sink vertex. 3 0 1 1 2 2 1 2 0 Would be a graph with 3 vertices and the edges { (0->1), (1->2), (2->1), (2->0) }, notice that there is a directed edge both from vertex 1 to 2 and vertex 2 back to 1. It is recommended that you use something similar to the following in the constructor for both lists. // Read in number of vertices. for (unsigned i = 0;i < vertices;++i) { // Initialize vertices } int source, sink; while(/* Can still read edges in */) { // Read in an edge // Add edge to adjacency list (push-back) } The string path(int sink) function will print out the path from the source to the sink vertex passed in. The format for this is {source->next->next->sink} with no whitespace. For example, a path from source 0 to vertex 2 to sink 1 would be output as: {0->2->1} For the dfs() and bfs() functions in your .cpp files, annotate the functions with their run times. In a comment above the function definition specify the runtime and space complexity of your implementation and in comments on each line put the run time of that line of code in your implementation. For helper function calls you don't need to annotate the function definitions. // Overall runtime complexity: O(?) // Overall space complexity: O(?) void foo() { int x = 5; // O(?) int y = bar; // O(?) } int bar() { return 5; // No annotations necessary }

CODE MUST BE DONE WITH THIS HEADER

#ifndef ADJACENCYLIST_H #define ADJACENCYLIST_H #include <vector> #include <string> using namespace std; class Graph { private: vector<int> _distances; vector<int> _previous; public: Graph() { } virtual int vertices() const = 0; virtual int edges() const = 0; virtual int distance(int) const = 0; virtual void bfs(int) const = 0; virtual void dfs(int) const = 0; virtual void display() const = 0; class AdjacencyList : public Graph { private: //Add what you need public: AdjacencyList(std::string filename); int vertices() const; int edges) const; int distance(int i) const; string path(int i) const; void bfs(int); void dfs(int); void display() const; #endif // _ADJACENCYLIST_H__

Answer 1

BFS() Implementation using Adjacency matrix

Input

You need to give

1. No of vertex in graph

2. No .of edges in graph

3. Start/ source vertex for BFS traversal

Code is

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

class Graph {

// Number of vertex
int v;

// Number of edges
int e;

// Adjacency matrix
int** adj;

public:
// To create the initial adjacency matrix
Graph(int v, int e);

// Function to insert a new edge
void addEdge(int source, int sink);

// Function to display the BFS traversal
void BFS(int start);
};

// Function to fill the empty adjacency matrix i.e making all elements as 0
Graph::Graph(int v, int e)
{
this->v = v;
this->e = e;
adj = new int*[v];
for (int row = 0; row < v; row++) {
adj[row] = new int[v];
for (int column = 0; column < v; column++) {
adj[row][column] = 0;
}
}
}

// Function to add an edge to the graph
void Graph::addEdge(int source, int sink)
{

// Considering a bidirectional edge
adj[source][sink] = 1;

}

// Function to perform BFS on the graph
void Graph::BFS(int start)
{
// We maintain a visited array to make sure that no vertex is visited more than once
// initially all are false and as soon we visited then we change the status to true
vector<bool> visited(v, false);
vector<int> q;
q.push_back(start);

// Set source as visited change status to true
visited[start] = true;

int vis;
while (!q.empty()) {
vis = q[0];

// Print the current node
cout << vis << " ";
q.erase(q.begin());

// For every adjacent vertex to the current vertex
for (int i = 0; i < v; i++) {
if (adj[vis][i] == 1 && (!visited[i])) {

// Push the adjacent node to the queue
q.push_back(i);

// Set
visited[i] = true;
}
}
}
}

// Driver code
int main()
{
int v , e,v1,v2 ;

// Create the graph
cout<<"Enter the number of vertices in graph ";
cin>>v;
cout<<"enter the number of edges in graph";
cin>>e;
Graph G(v, e);
cout<<"Enter edges by indicating source and sink vertex";
for(int i=0;i<e;i++)
{
cin>>v1>>v2;
G.addEdge(v1, v2);
}
int source;
cout<<"Enter the source vertex of BFS";
cin>>source;
// Perform B

C. (USCIS[Juunaliu vei Desktopless programy Uisusingmatrix.exe Enter the number of vertices in graph 3, enter the number of edges in graph 4, Enter edges by indicating source and sink vertex 01 1 2 21 20 Enter the source vertex of BFS O BFS Traversal 0 1 2 Process returned o (@x0) execution time : 32.833 s Press any key to continue.

BFS
cout<<"BFS Traversal"<<endl;
G.BFS(source);
}

Output ( See output is for the graph given in question if u want to test over any other input you can do it easily)

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.

But as we are using adjacency matrix so it become O(V^2)

as to find neighbor we need two loop for searching 1 in matrix

Space Complexity is s O(w) where w is the maximum width of the tree.

Now

DFS() Implementation using Adjacency matrix

Input

You need to give

1. No of vertex in graph

2. No .of edges in graph

3. Start/ source vertex for DFS traversal

Code is

// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;

class Graph {

// Indicate Number of vertex
int v;

// Number of edges
int e;

// Adjacency matrix
int** adj;

public:
// To create the initial adjacency matrix
Graph(int v, int e);

// Function to insert a new edge
void addEdge(int source, int sink);

// Function to display the DFS traversal
void DFS(int start, vector<bool>& visited);
};

// Function to fill the empty adjacency matrix
Graph::Graph(int v, int e)
{
// making all positions in matrix as 0
this->v = v;
this->e = e;
adj = new int*[v];
for (int row = 0; row < v; row++) {
adj[row] = new int[v];
for (int column = 0; column < v; column++) {
adj[row][column] = 0;
}
}
}

// Function to add an edge to the graph
void Graph::addEdge(int source, int sink)
{

// Considering a directional edge as directed graph is given so only that position as 1
adj[source][sink] = 1;

}

// Function to perform DFS on the graph
void Graph::DFS(int start, vector<bool>& visited)
{

// Print the current node
cout << start << " ";

// Set current node as visited
visited[start] = true;

// For every node of the graph
for (int i = 0; i < v; i++) {

// If some node is adjacent to the current node
// and it has not already been visited
if (adj[start][i] == 1 && (!visited[i])) {
DFS(i, visited);
}
}
}

// Driver code
int main()
{
int v , e,v1,v2 ;

// Create the graph
cout<<"Enter the number of vertices in graph ";
cin>>v;
cout<<"enter the number of edges in graph";
cin>>e;
Graph G(v, e);
cout<<"Enter edges by indicating source and sink vertex";
for(int i=0;i<e;i++)
{
cin>>v1>>v2;
G.addEdge(v1, v2);
}

// Visited vector to so that
// a vertex is not visited more than once
// Initializing the vector to false as no
// vertex is visited at the beginning
vector<bool> visited(v, false);
int source;
cout<<"Enter the source vertex of DFS";
cin>>source;
// Perform DFS
cout<<"DFS Traversal"<<endl;
G.DFS(source, visited);
}

Output ( See output is for the graph given in question if u want to test over any other input you can do it easily)

- D "C:\Users\Sudhanshu Goel\Desktop\ces3 c programing\dfsusingmatrix.exe" Enter the number of vertices in graph 3 enter the number of edges in graph 4, Enter edges by indicating source and sink vertex 01 1 2 2 1 20 Enter the source vertex of DFS DFS Traversal 0 1 2 Process returned 0 (0x0) execution time : 39.274 s Press any key to continue.

Time Complexity: O(V+E) where V is number of vertices in the graph and E is number of edges in the graph.

But as we are using adjacency matrix so it become O(V^2)

as to find neighbor we need two loop for searching 1 in matrix

Space Complexity is O(H) i.e what is max height of the tree