Data Structure in C++ I need help wtih the create and print commands thank you!
ID: 3842427 • Letter: D
Question
Data Structure in C++
I need help wtih the create and print commands thank you!
Implement the following commands Command Description create n r Create a new empty graph in register r, with n nodes print r Print some representation of the graph in r arc a b r In the graph in register r, create an arc from node a to b biarc a b r Create a bidirectional arc from a to b in r bfs a b r Perform a breadth-first search from a to b in r, printing the distance Write the register commands necessary to create the following graph: alpha place them in a comment in your source code. What is the distance from node 9 to node 6?Explanation / Answer
Answer
An empty graph with n nodes can be represented as an adjacency list with zero values.
C++ code for the same is as below:
#include <iostream.h>
#include <stdlib.h>
// an adjacency list node represented by below structure
struct Adj_List_Node
{
int dest;
struct Adj_List_Node* next;
};
// an adjacency list structure
struct Adj_List
{
struct Adj_List_Node *head;
// this is the pointer to head node of list
};
// a graph represented by structure. A graph is represented as an array of adjacency lists.
// V, i.e. the number of vertices, will represent the Size of array
struct Graph
{
int V;
struct Adj_List* array;
};
// this is a utility function that creates a new adjacency list node
struct Adj_List_Node* new_Adj_List_Node(int dest)
{
struct Adj_List_Node* newNode =
(struct Adj_List_Node*) malloc(sizeof(struct Adj_List_Node));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
// this is a utility function that creates a graph of V vertices
struct Graph* createGraph(int V)
{
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
// this creates an array of adjacency lists
graph->array = (struct Adj_List*) malloc(V * sizeof(struct Adj_List));
// Initializing each adjacency list with 0 to indicate they are empty by making head as NULL
int i;
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
//Since the graph is empty, no edge is being added
// and the addedge() has been omitted
// this funtion prints the adjacenncy list representation of graph
void printGraph(struct Graph* graph)
{
int v;
for (v = 0; v < graph->V; ++v)
{
struct Adj_List_Node* pCrawl = graph->array[v].head;
cout<<" The adjacency list of vertex "<<v<<" head ";
while (pCrawl)
{
cout<<"-> "<< pCrawl->dest;
pCrawl = pCrawl->next;
}
cout<<" ";
}
}
int main()
{
// create the graph given in above fugure
int V = 0;
struct Graph* graph = createGraph(V);
// print the adjacency list representation of the above graph
printGraph(graph);
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.