The reason for this constraint is that you can algorithmically initialize an adj

Question

The reason for this constraint is that you can algorithmically initialize an adjacency matrix with a perfect square size grid quite simply. If you draw out adjacency matrices for 2x2 or 3x3 etc., you should see the pattern.
2) Construct a minimal spanning tree from the gridgraph, thereby producing a maze. We will use the idea of minimal spanning trees to enable us to produce different mazes. When your program runs, the gridgraph will have arbitrarily assigned weights for the edges, different every time. This will ensure that your program creates a different maze every time. You will use Prim's algorithm to produce the MST. The following is a Spanning tree for the gridgraph above:

3) From the minimal spanning tree, the actual maze will be produced. We will use asterisks to draw a text-based representation of our maze. The entrance will always be top-left and the exit will always be bottom right, where asterisks will be omitted. The maze for the above MST would look like this:

When the program runs, it will draws new mazes by asking the user for the size of the maze (a perfect square) or -1 to quit. With a proper size, it draws a new maze on the console. With -1, the program terminates. With any other number, it re-prompts for legal input.

Explanation / Answer

//C program to implement the Graph Traversal
//(a) Breadth first traversal
//(b) Depth first traversal


#include<stdio.h>                                //For standard input/output functions#include<stdlib.h>                               //For standard library functions
void dfs();                                            // For Deapth First Search(DFS) Traversal
void bfs();    // For Breadth First Search(BFS) Traversal

struct link                                            // Structure for adjacency list
{
struct node *next;
struct link *adj;
};

struct node                                          // Structure for elements in the graph
{
int data,status;
struct node *next;
struct link *adj;
};

struct node *start,*p,*q;                   //Declaring pointer variable for structure node
struct link *l,*k;                                 //Declaring pointer variable for structure node

void create()                                        // Function to Create the graph
{
int dat,flag=0;dat=1;                          //Initializing 'flag' & 'dat' with a value of '0' & '1'start=NULL;                                      //'start' pointing to NULL, as no value is being input till nowprintf("Enter the nodes in the graph(0 to end): ");
while(dat)
{
scanf("%d",&dat);                           //Getting the data from user
if(dat==0)                                    //If data entered is '0' then assume its the end of inputting elements
break;
p=(struct node*)malloc(sizeof(struct node));  //reserving memory space for nodal element p->data=dat;                                                       //storing the input data into node's data element
p->status=0;
p->next=NULL;                                                 //next element is set to NULL p->adj=NULL;                                                   //previous element is set to NULL
if(flag==0)                                                          //If flag's value is zero then follow below procedure
{
start=p;
q=p;
flag++;
}                                                                            //If flag's value is not zero then follow below methodelse
{
q->next=p;
q=p;
}
}                                                                           //Finishing the data entry loopp=start;                                                               //Assigning the pointer 'p' the starting locationwhile(p!=NULL)
{                                                    
printf("Enter the links to %d (0 to end) : ",p->data);
flag=0;                                                                //Setting the initial value of 'flag' be '0'
while(1)
{
scanf("%d",&dat);
if(dat==0)
break;
k=(struct link*)malloc(sizeof(struct link));          //Allocating memory space for "link" element k->adj=NULL;
if(flag==0)
{
p->adj=k;
l=k;
flag++;
}
else
{
l->adj=k;
l=k;
}
q=start;
while(q!=NULL)
{
if(q->data==dat)
k->next=q;
q=q->next;
}
}
p=p->next;
}
}

void bfs()                        //Function for Breadth First Traversal of Graph
{
int q[20],i=1,j=0;
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
q[0]=p->data;
p->status=1;
while(1)
{
if(q[j]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==q[j])
break;
p=p->next;
}
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
q[i]=q->data;
q->status=1;
q[i+1]=0;
i++;
}
k=k->adj;
}
j++;
}
j=0;
printf("Breadth First Search Results ");
while(q[j]!=0)                                               //For printing the BFS result array
{
printf("%d ",q[j]);                     
j++;
}
getche();

}//Function for Depth First Search(BFS) Traversal.
void dfs()
{
int stack[20],top=1;
printf("Deapth First Search Results");
p=start;
while(p!=NULL)
{
p->status=0;
p=p->next;
}
p=start;
stack[0]=0;
stack[top]=p->data;
p->status=1;
while(1)
{
if(stack[top]==0)
break;
p=start;
while(p!=NULL)
{
if(p->data==stack[top])
break;
p=p->next;
}
printf("%d ",stack[top]);        //Printing the DFS result
top--;
k=p->adj;
while(k!=NULL)
{
q=k->next;
if(q->status==0)
{
top++;
stack[top]=q->data;
q->status=1;
}
k=k->adj;
}
}
}

int main()
{
int ch;
create();                               //Invoking the create function
while(1)
{
printf("1: DFS 2: BSF 0: Exit Enter your choice: ");
scanf("%d",&ch); //User enters his choice
switch(ch)
{
case 1:
dfs();                                   //For Depth First Traversal
break;
case 2:
bfs();                                  //For Breadth First Traversal
break;
case 0:
exit(0);                             //If Zero then exit the program (Omit this line if you don't want that)
break;
default:
printf("Incorrect choice!");
}
}
return 0;
}                                       //End of program

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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