Q) Write a program to create a graph use the map of any city as the graph.
Represent graph as adjacency
matrix/list and perform depth first search and breadth first search.
#include<stdio.h>
#include<stdlib.h>
#define MAX 10
struct AdjListw
{
int dest;
struct AdjListw* next;
};
struct AdjList
{
struct AdjList *head;
};
struct Graph
{
int V;
struct AdjList* array;
};
struct AdjListw* newAdjListw(int dest)
{
struct AdjListw* newNode =
(struct AdjListw*) malloc(sizeof(struct AdjListw));
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 AdjListw* newNode = newAdjListw(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListw(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 AdjListw* pCrawl = graph->array[v].head;
printf("\n Adjacency list of vertex %d\n head ", v);
while (pCrawl)
{
printf("-> %d", pCrawl->dest);
pCrawl = pCrawl->next;
}
printf("\n");
}
}
int isNotVisited(int v, int visited[], int n)
{
int i;
for(i = 0; i < n; i++)
if(v == visited[i])
return 0;
return 1;
}
void DFS(struct Graph* graph, int v, int visited[], int n)
{
visited[v] = 1;
printf("%d ", v);
struct AdjListw* pCrawl = graph->array[v].head;
while(pCrawl)
{
if(isNotVisited(pCrawl->dest, visited, n))
DFS(graph, pCrawl->dest, visited, n);
pCrawl = pCrawl->next;
}
}
void BFS(struct Graph* graph, int v, int visited[], int n)
{
int queue[MAX], front = 0, rear = 0;
visited[v] = 1;
queue[rear] = v;
rear++;
while(front < rear)
{
v = queue[front];
front++;
printf("%d ", v);
struct AdjListw* pCrawl = graph->array[v].head;
while(pCrawl)
{
if(isNotVisited(pCrawl->dest, visited, n))
{
visited[pCrawl->dest] = 1;
queue[rear] = pCrawl->dest;
rear++;
}
pCrawl = pCrawl->next;
}
}
}
int main()
{
int n, i, j;
printf("Enter the number of cities: ");
scanf("%d", &n);
struct Graph* graph = createGraph(n);
int visited[n];
for(i = 0; i < n; i++)
visited[i] = 0;
printf("Enter the roads in the format (source destination):\n");
while(1)
{
scanf("%d%d", &i, &j);
if(i == -1 && j == -1)
break;
addEdge(graph, i, j);
}
printf("\nAdjacency List:\n");
printGraph(graph);
printf("\nDFS traversal:\n");
for(i=0; i < n; i++)
if(visited[i] == 0)
DFS(graph, i, visited, n);
for(i = 0; i < n; i++)
visited[i] = 0;
printf("\nBFS traversal:\n");
for(i=0; i < n; i++)
if(visited[i] == 0)
BFS(graph, i, visited, n);
return 0;
}