In this assignment you will write an algorithm that determines whether there is
ID: 3804571 • Letter: I
Question
In this assignment you will write an algorithm that determines whether there is a path through a maze. A maze will be represented as an undirected graph with each room represented as a vertex and each corridor represented as a pair of edges. Each room will be uniquely identified by a single character label.
Here are two sample mazes that will be used to test your implementation (notice that maze #1 has a path from the entrance to exit but maze #2 does not):
a) (9 points) Implement the following function:
int isExitReachable(Graph *pMaze, char entrance, char exit);
This function should return whether a path exists from entrance to exit. A non-zero return value indicates that a path exists; a zero return value indicates that no path exists.
Demonstrate your function working with mazes #1 & #2. Note, your implementation must be generic (i.e. work with any maze) even though you are only required to demonstrate success with mazes #1 & #2.
(entrance) Maze #1 exit (entrance) (exit) Maze #2Explanation / Answer
#include<stdio.h>
#include<stdlib.h>
struct AdjListNode//Representing one edge from source vertex to destination vertex
{
char dest;
struct AdjListNode *next;//Linked list of all adjacent nodes to one vertex
};
struct AdjList//Representing vertex
{
struct AdjListNode *head;//Pointer to adjacent list of all vertices from this vertex
int visited;//Flag to represent this particular vertex is visited or not
};
struct Graph//
{
int v;//No of vertices
struct AdjList *array;//Array of AdjList
};
struct Graph * create_graph(int v)//Initialization function
{
struct Graph *temp = (struct Graph *)malloc(sizeof(struct Graph));//Allocating memroy
temp -> v = v;//initializing number of vertices in a graph
temp->array = (struct AdjList *)malloc(v*sizeof(struct AdjList));//Allocating array of vertices(AdjList)
int i = 0;
for(i=0; i<v ; i++)
{
temp->array[i].visited=0;//Making visited = 0 initially
temp->array[i].head = NULL;//Adjacent list not yet formed
}
return temp;
}
void add_edge(struct Graph * graph,char src,char dest)//forming edges
{
src=src-'A';//Array index starts from 0 so, if src is 'A' if you do 'A'-'A'== 0
struct AdjListNode *temp = (struct AdjListNode *)malloc(sizeof(struct AdjListNode));//Creating edge
temp ->dest = dest;
temp->next = graph->array[src].head;//Forming linked list of adjacent vertices
graph->array[src].head = temp;
return;
}
int isExitReachable(struct Graph *graph,char entrance,char exit)//Traversing the graph using depth first search(DFS) from entrance
{
graph->array[entrance-'A'].visited=1;//If vertex is traversed, we will make the flag visited = 1, so that we will traverse again
if(entrance==exit)//if we reach exit, entrance becomes exit, that means we reached the exit from entrance, which means there is a path.
return 1;
struct AdjListNode *temp;
for(temp = graph ->array[entrance-'A'].head;temp!=NULL;temp=temp->next)//Getting adjacent lists and traverse which is called as DFS
{
int adj_vert = temp->adj_vert;
if(!graph->array[adj_vert-'A'].visited)
{
if(isExitReachable(graph,entrance,adj_vert,exit))
return 1;
}
}
return 0;//means there is no path between entrance and exit
}