Data Structures and Algorithms - Old Questions
13. Write short notes on (any two):
a) Queue in circular linked list
b) ADT
c) MST (Minimum Cost Spanning Tree) of a graph.
a) Queue in Circular Linked List
By using a circular list, a queue may be specified by a single pointer q to that list. node(q) is the rear of the queue and the following node is its front.
Insertion function:
void insert(int item)
{
NodeType *nnode;
nnode=( NodeType *)malloc(sizeof(NodeType));
nnode->info=item;
if(pq==NULL)
pq=nnode;
else
{
nnode->next=pq->next;
pq->next=nnode;
pq=nnode;
}
}
Deletion function:
void delet(int item)
{
NodeType *temp;
if(pq==NULL)
{
printf(“void deletion\\n”);
exit(1);
}
else if(pq->next==pq)
{
printf(“poped item=%d”, pq->info);
pq=NULL;
}
else
{
temp=pq->next;
pq->next=temp->next;
printf(“poped item=%d”, temp->info);
free(temp);
}
}
b) ADT
Abstract data types are a set of data values and associated operations that are precisely independent of any particular implementation. Generally the associated operations are abstract methods. E.g. stack, queue etc.
c) MST (Minimum Cost Spanning Tree) of a graph
A spanning tree is a subset of Graph G, which has all the vertices of G with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected.
In a weighted graph, a minimum spanning tree (MST) is a spanning tree that has minimum weight than all other spanning trees of the same graph.
There are three different algorithms to construct the minimum spanning tree:
- Prim’s algorithm: Grows the tree in stages. Selects an edge with lowest cost that can be added to the tree without forming cycle.
- Kruskal’s algorithm: In each stage select the edge in non-decreasing order of cost.
- Sollin’s algorithm: Select several edges at each stage.