Data Structure using C++ only C++ please write 3 different codes as graph.h grap

Question

Data Structure using C++ only C++

please write 3 different codes as graph.h graph.cpp and main.cpp

1) Implement a graph using an edge list, adjacency matrix, or adjacency list structure. The graph much contain an add_edge(), and add_node() function. You may construct your graph in your main function. Once you have constructed your graph you must implement a Breadth first search and execute the breadth on your constructed graph. Display the nodes in the order that they are visited by your breadth first search.

Explanation / Answer

// File Name: GraphUsingAdjacencyMatrix.h
#ifndef GRAPHUSINGADJACENCYMATRIX_H
#define GRAPHUSINGADJACENCYMATRIX_H
#define MAX 20

// Defines Graph
class Graph
{
private:
// Data member to store number of node
int nodes;
// To store adjacency matrix values
int ** adjacency;
// To store visited node status
bool *visited;
public:
// Function to add number of nodes
void add_node(int nodes);
// Function to add edges
void add_edge(int origin, int destination);
// Function to display the graph
void showGraph();
};// End of class

#endif

--------------------------------------------------------------------------

// File Name: GraphUsingAdjacencyMatrix.cpp
#include"GraphUsingAdjacencyMatrix.h"
#include <iostream>
using namespace std;

// Function to add number of nodes
void Graph :: add_node(int nodes)
{
// Assigns parameter nodes to data member nodes
this->nodes = nodes;
// Dynamically creates boolean array for storing visited status
visited = new bool [nodes];
// Dynamically allocates memory for number of rows for the adjacency matrix
adjacency = new int* [nodes];
// Loops till number of nodes for each row
for (int row = 0; row < nodes; row++)
{
// Dynamically allocates memory to each column for each row of the adjacency matrix
adjacency[row] = new int [nodes];
// Loops till number of nodes for each column
for(int col = 0; col < nodes; col++)
{
// Assigns zero to each cell of the adjacency matrix
adjacency[row][col] = 0;
}// End of inner for loop
}// End of outer for loop
}// End of function

// Function to add edges
void Graph :: add_edge(int origin, int destination)
{
// Checks if origin is greater than or equals to the number of nodes
// Or destination is greater than or equals to number of nodes
// or origin or destination is negative
if( origin > nodes || destination > nodes || origin < 0 || destination < 0)
// Displays error message
cout<<"ERROR: Invalid edge! ";
// Otherwise valid
else
// Adds one to the origin and destination minus one index position to one
adjacency[origin - 1][destination - 1] = 1;
}// End of function

// Function to display the graph
void Graph :: showGraph()
{
// Loops till number of nodes for each row
for(int row = 0; row < nodes; row++)
{
// Loops till number of nodes for each column
for(int col = 0; col < nodes; col++)
{
// Displays the matrix data
cout<<adjacency[row][col]<<" ";
}// End of inner for loop
cout<<endl;
}// End of outer for loop
}// End of function

-------------------------------------------------------------------------------

// File Name: GraphUsingAdjacencyMatrixMain.cpp
#include "GraphUsingAdjacencyMatrix.cpp"
#include <iostream>
using namespace std;

// main method definition
int main()
{
// Local variable for number of nodes, maximum edges, origin, destination
int nodes, maximumEdges, origin, destination;

// Declares a graph object
Graph graph;

// Accepts number of nodes from the user
cout<<"Enter number of nodes: ";
cin>>nodes;

// Calls the method to add nodes
graph.add_node(nodes);

// Calculates maximum edges
maximumEdges = nodes * (nodes - 1);

// Loops till number of edges
for (int counter = 0; counter < maximumEdges; counter++)
{
// Accepts the edges from the user for adjacency matrix
cout<<"Enter edge (-1 -1 to exit): ";
cin>>origin>>destination;
// Checks if the origin and destination data entered by the user is -1 then stop
if((origin == -1) && (destination == -1))
// Come out of the loop
break;
// Calls the function to add edges to adjacency matrix
graph.add_edge(origin, destination);
}// End of for loop
// Calls the function to show the graph
graph.showGraph();
return 0;
}// End of main function

Sample Output:

Enter number of nodes: 6
Enter edge (-1 -1 to exit): 1 2
Enter edge (-1 -1 to exit): 4 3
Enter edge (-1 -1 to exit): 1 5
Enter edge (-1 -1 to exit): 2 3
Enter edge (-1 -1 to exit): 1 4
Enter edge (-1 -1 to exit): 5 2
Enter edge (-1 -1 to exit): 3 1
Enter edge (-1 -1 to exit): 2 5
Enter edge (-1 -1 to exit): 6 1
Enter edge (-1 -1 to exit): 8 4
ERROR: Invalid edge!
Enter edge (-1 -1 to exit): 3 4
Enter edge (-1 -1 to exit): -1 -1
0 1 0 1 1 0
0 0 1 0 1 0
1 0 0 1 0 0
0 0 1 0 0 0
0 1 0 0 0 0
1 0 0 0 0 0

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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