Data Structure using C++ please write 3 different codes as graph.c graph.cpp and

Question

Data Structure using C++

please write 3 different codes as graph.c 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: GraphBreadthFirstSearch.cpp
#include<iostream>
#include<stdlib.h>

#define MAX 100

#define initial 1
#define waiting 2
#define visited 3
using namespace std;

// To store number of vertices
int numberOfVertices;
// For adjacency matrix
int adjacencyList[MAX][MAX];
// For current state of each node
int currentState[MAX];
// For queue operation
int myQueue[MAX], frontEnd = -1, rearEnd = -1;

// Function to return one if queue is empty otherwise zero
int isEmptyQueue()
{
// Checks if front is -1 or front is greater than read then queue is empty
if(frontEnd == -1 || frontEnd > rearEnd)
return 1;
// Otherwise not empty
else
return 0;
}// End of function

// Function to delete an vertex from the queue and returns it
int deleteQueue()
{
// To store the deleted item
int deleteItem;

// Checks if front is -1 or front is greater than read then queue is empty
if(frontEnd == -1 || frontEnd > rearEnd)
{
cout<<"Queue Underflow ";
exit(1);
}// End of if condition
// Stores the front vertex of the queue in deletedItem
deleteItem = myQueue[frontEnd];
// Increase the front counter by one
frontEnd = frontEnd + 1;
// Return the deleted vertex
return deleteItem;
}// End of function

// Function to insert an vertex from the queue
void insertQueue(int vertex)
{
// Checks if read is equals to maximum -1 then queue is full
if(rearEnd == MAX-1)
cout<<"Queue Overflow ";
// Otherwise queue is not full
else
{
// Checks if the front is -1 then first node
if(frontEnd == -1)
// Set the front to zero
frontEnd = 0;
// Increase the read counter by one
rearEnd = rearEnd + 1;
// Adds the vertex to the queue
myQueue[rearEnd] = vertex;
}// End of else
}// End of function

// Helper function for BFS traversal
// Receives the starting vertex as parameter
void BFS(int ver)
{
// Loop variable
int counter;
// Insert the starting vertex in the queue
insertQueue(ver);
// Set the starting vertex to waiting status
currentState[ver] = waiting;

// Loops till queue is not empty
while(!isEmptyQueue())
{
// Delete the vertex
ver = deleteQueue( );
// Display the vertex
cout<<ver<<" ";
// Set the current vertex as visited status
currentState[ver] = visited;

// Loops till number of vertex
for(counter = 0; counter < numberOfVertices; counter++)
{
// Checks if the adjacency list current vertex and current position data is one
// and current state of the vertex is initial
if(adjacencyList[ver][counter] == 1 && currentState[counter] == initial)
{
// Insert into the queue
insertQueue(counter);
// Set the current vertex as waiting status
currentState[counter] = waiting;
}// End of if condition
}// End of for loop
}// End of while loop
cout<<endl;
}// End of function

// Main function for BFS traversal
void BFSTraversal()
{
// To store the starting vertex
int ver;
// Loops till number of vertex
for(ver = 0; ver < numberOfVertices; ver++)
// Set the each vertex to initial value
currentState[ver] = initial;
// Accept the starting vertex from the user
cout<<" Enter Start Vertex for BFS: ";
cin>>ver;
// Calls the helper function for BFS traversal
BFS(ver);
}// End of function

// Function to generate graph
void generateGraph()
{
int counter, maximumEdge, origin, destin;
// Accepts number of vertex
cout<<" Enter number of vertices : ";
cin>>numberOfVertices;
// Generates maximum edges
maximumEdge = numberOfVertices * (numberOfVertices - 1);

// Loops till number of edges
for(counter = 1; counter <= maximumEdge; counter++)
{
// Accepts edges till it is not -1
cout<<" Enter edge %d( -1 -1 to quit "<<counter<<": ";
cin>>origin>>destin;

// Checks if the origin and destination is -1 then stop
if((origin == -1) && (destin == -1))
break;

// Checks if origin is greater than or equals to the number of vertex
// Or destination is greater than or equals to number of vertex
// or origin or destination is negative
if(origin >= numberOfVertices || destin >= numberOfVertices || origin < 0 || destin < 0)
{
cout<<"Invalid edge! ";
// Decrease the counter by one
counter--;
}// End of if condition
// Otherwise valid data
else
adjacencyList[origin][destin] = 1;
}// End of for loop
}// End of function

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

// File Name: GraphBFSMain.c
#include "GraphBreadthFirstSearch.c"
// main function definition
int main()
{
// Calls the function to generate graph
generateGraph();
// Calls the function for BFS traversal
BFSTraversal();
return 0;
}// End of main function

Sample Output:

Enter number of vertices : 6
Enter edge 1( -1 -1 to quit ) : 2 1
Enter edge 2( -1 -1 to quit ) : 3 5
Enter edge 3( -1 -1 to quit ) : 6 1
Invalid edge!
Enter edge 3( -1 -1 to quit ) : 2 4
Enter edge 4( -1 -1 to quit ) : 3 1
Enter edge 5( -1 -1 to quit ) : 1 0
Enter edge 6( -1 -1 to quit ) : 3 4
Enter edge 7( -1 -1 to quit ) : 3 1
Enter edge 8( -1 -1 to quit ) : 4 2
Enter edge 9( -1 -1 to quit ) : -1 -1
Enter Start Vertex for BFS:
2
2 1 4 0

Related Questions

Navigate

• Browse (All)
• Browse D
• Subjects

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