I am having a difficult time with this question using C++ programming. Can someo
ID: 3776357 • Letter: I
Question
I am having a difficult time with this question using C++ programming. Can someone help? Implement a class for a weighted directed graph using an adjacency matrix. The class should have a constructor, a copy constructor, a destructor and all the methods necessary to add/delete vertices, add/delete edges… Write a menu-driven program to THOROUGHLY check your class and all the methods included in your program. You can choose the data type for the list. Allow the user to continue with operations as long as he/she wants to. Your program should check if an operation is possible ( ex: check if the graph is empty before attempting to delete an item; check if it is full before attempting to insert an item…) Your program should have the following methods: 1. A DFS method to perform a Depth First Search from a given vertex 2. A BFS method to perform a Breadth First Search from a given vertex 3. A shortestPath method that print the shortest path from a given vertex v to any other vertex 4. Additional methods that will make your program more structured.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
struct AdjList
{
struct AdjListNode *head;
};
struct Graph
{
int V;
struct AdjList* array;
};
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(src);
newNode->next = graph->array[dest].head;
graph->array[dest].head = newNode;
}
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct AdjListNode* pCrawl = graph->array[v].head;
printf(" Adjacency list of vertex %d head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf(" ");
}
}
int main()
{
// create the graph given in above fugure
int V = 5;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.