Output: Write a C++ or Java class definition for an abstract data type called Gr

Question

Output:

Write a C++ or Java class definition for an abstract data type called Graph that models an undirected graph. Implement the following public member functions: A constructor that creates an empty graph An appropriate destructor. No need if you use Java. void load (char *filename): Creates the graph using the file passed into the function. The format of the file is described later. You may assume load is only called once for a graph. You may modify the argument type of this function if you use Java. void display ():Displays the graph's adjacency matrix to the screen. void displayDFS (int vertex): Displays the result of a depth first search starting at the provided vertex. When you have a choice between selecting two vertices, pick the vertex with the lower number void displayBFS (int vertex): Displays the result of a breadth first search starting at the provided vertex. When you have a choice between selecting two vertices, pick the vertex with the lower number You are permitted to add extra member functions you feel are helpful. DFS must be implemented using recursion. You can use "queue" in STL in the implementation of BFS Other forms of using STL are not permitted Additional requirements and reminders: Loops are allowed but multiple edges are not allowed. Vertices are labeled numerically from 0 to n-1 where n is the number of vertices in the graph If using C++, name your files Graph.h, Graph.cpp and HW4.cpp. If using Java, name your files Graph.java and HW4.java.

Explanation / Answer

Source Code:-
#include<iostream>
#include<stdlib.h>
#include<fstream>
#define MAX 5
using namespace std;
class DFS
{
public:
int visited[MAX];
int size;
int **adj_matrix;
DFS()
{
adj_matrix= (int **)malloc(sizeof(int *) * MAX);
adj_matrix[0] = (int *)malloc(sizeof(int) * MAX * MAX);
for(int i=0;i<MAX;i++)
adj_matrix[i] =(*adj_matrix+MAX*i);
}
~DFS()
{
}
public:
void load(char *filename)
{
ifstream file;
file.open(filename);
file>>size;
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
file>>adj_matrix[i][j];
}
}
for (int i=0;i<=size;i++)
{
visited[i] = 0;
}
}
public:
void Display()
{
cout<<" *** The Adjacency Matrix Elements are***"<<endl;
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
cout<<adj_matrix[i][j]<<" ";
}
cout<<endl;
}
}
void DisplayDFS(int vertex)
{
int i;
visited[vertex] = 1;
cout << vertex << " ";
for(i=1;i<=size;i++)
if (adj_matrix[vertex][i] && !visited[i])
DisplayDFS(i);
}
};
class BFS
{
public:
int visited[MAX];
int size;
int **adj_matrix;
BFS()
{
adj_matrix= (int **)malloc(sizeof(int *) * MAX);
adj_matrix[0] = (int *)malloc(sizeof(int) * MAX * MAX);
for(int i=0;i<MAX;i++)
adj_matrix[i] =(*adj_matrix+MAX*i);
}
~BFS()
{
}
void load(char *filename)
{
ifstream file;
file.open(filename);
file>>size;
for(int i=0;i<size;i++)
{
for(int j=0;j<size;j++)
{
file>>adj_matrix[i][j];
}
}
for (int i=0;i<=size;i++)
{
visited[i] = 0;
}
}
void DisplayBFS(int source)
{
int queue[MAX];
int i, front, rear, root;
front = rear = 0;
visited[source] = 1;
queue[rear++] = source;
cout<<source<<" ";
while(front != rear)
{
root = queue[front];
for(i=1;i<=size;i++)
if (adj_matrix[root][i] && !visited[i])
{
visited[i] = 1;
queue[rear++] = i;
cout<<i<<" ";
}
front++;
}
}
};
int main()
{
int source;
DFS depth;
BFS breadth;
char filename[]="matrix.txt";
cout<<" ****DFS Traversal******"<<endl;
depth.load(filename);
depth.Display();
cout<<" Enter the Source : ";
cin>>source;
cout<<" The nodes visited in the DFS order is :";
depth.DisplayDFS(source);
depth.load(filename);
cout<<" ****BFS Traversal******"<<endl;
cout<<" The nodes visited in the BFS order is :";
breadth.DisplayBFS(source);
return 0;
}


Sample Output:-
------------------------------

Related Questions

Navigate

• Browse (All)
• Browse O
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.