Answered step by step
Verified Expert Solution
Question
1 Approved Answer
Write a C++ or Java class definition for an abstract data type called Graph that models an undirected graph. Some implementation details Loops are allowed
Write a C++ or Java class definition for an abstract data type called Graph that models an undirected graph. Some implementation details Loops are allowed but multiple edges are not allowed. Vertices are labeled by number from 0 to n-1 where graph. is the number of vertices in the Implement the following public member functions. r 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. Input File Format The function load is responsible for reading in a file corresponding to a graph. The format is as follows: . The first line contains a single integer indicating how many vertices are present in the graph. You may make no assumptions on how many vertices in the graph - this means that your constructor will have to use dynamic allocation All remaining lines contain two integers that indicate an edge connects the two vertices o You can assume that the file exists and is well formed. As an example, the following graph is represented by the file: 0 1 1 2 2 4 3 2 4 0 1 3 2 4 Test Driver Program The program must accept the name of an input file as a command line argument. Create a main function that does the following: 1. Create an empty graph 2. Loads the graph using the specified input file. 3. Display the adjacency matrix. 4. Display a depth first search starting at vertex 0. 5. Display a breadth first search starting at vertex 0. Files Some files are available on Canvas * graph0.txt graphl.txt .graph2.txt . graph3.txt The outputs for these files are in the program output section Program Output Here is the output for the four provided input files: graph0.txt: Adjacency Matrix 0 011 0 0 0 0 0 1 1 100 1 1 0 0 0 10 1 1 0 0 0 11 0 1 0 0 0 11 0011 1 0 0 0 001 10 0 DFS at vertex 0:0213546 BFS at vertex 0:023156 4 graphl.txt: Adjacency Matrix 01 00 1 1 011 0 010 1 1 011 0 0 101 0 0 DFS at vertex 0: 01 2 3 4 BFS at vertex 0:0 1 4 2 3 graph2.txt: Adjacency Matrix 010 1 0 000 0 010 0 0 1 0 0 0 11 0 0 1 0 1 0 0 010 1 0 1 0 1 0 001 0 1 0 011 000 1 0 00 1 0 000 011 1 0 1 000 00 1 0 1 0 DFS at vertex 0: 01 2 5 4 3 678 BFS at vertex 0: 0 1 3 2 4 6 5 7 8 graph3.txt Adjacency Matrix 011 1 1 0 101011 1 1 0 10 0 101 0 11 11 0 1 01 0 1 011 0 DFS at vertex 0: 0 1 2 3 4 5 BFS at vertex 0: 0 1 2 3 45
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started