#include <stdio.h>
#include <stdlib.h>
#include<conio.h>
struct AdjListNode
{
int dest;
struct AdjListNode* next;
};
struct AdjList
{
struct AdjListNode *head;
};
struct AdjListNode* head1=NULL;
struct Graph
{
int V;
struct AdjList* array;
};
struct AdjListNode* newAdjListNode(int dest)
{
struct AdjListNode* newNode =
(struct AdjListNode*) malloc(sizeof(struct AdjListNode));
newNode->dest = dest;
newNode->next = NULL;
return newNode;
}
struct Graph* createGraph(int V)
{
int i;
struct Graph* graph = (struct Graph*) malloc(sizeof(struct Graph));
graph->V = V;
graph->array = (struct AdjList*) malloc(V * sizeof(struct AdjList));
for (i = 0; i < V; ++i)
graph->array[i].head = NULL;
return graph;
}
void addEdge(struct Graph* graph, int src, int dest)
{
struct AdjListNode* newNode = newAdjListNode(dest);
newNode->next = graph->array[src].head;
graph->array[src].head = newNode;
newNode = newAdjListNode(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 AdjListNode* 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 bfs(struct Graph* graph, int s1, int f)
{
int visited[100],i,s;
struct AdjListNode* pCrawl,*temp,*temp1,*head;
head1=NULL;
for(i=0;i<graph->V;i++) visited[i]=0;
head1=(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
head1->dest=s1;
head1->next=NULL;
visited[s1]=1;
s=s1;
while(head1!=NULL&&visited[f]==0){
pCrawl = graph->array[s].head;
while (pCrawl!=NULL&&visited[f]==0){
if( visited[pCrawl->dest]==0){
visited[pCrawl->dest]=1;
temp=(struct AdjListNode*)malloc(sizeof(struct AdjListNode));
temp->dest=pCrawl->dest;
temp->next=NULL;
head1->next=temp;
}
pCrawl=pCrawl->next;
}
while(head!=NULL&&visited[f]==0){
temp=head1;
temp=temp->next;
head1=temp;
}
s=head1->dest;
if( visited[s1]==1&&visited[f]==1) return 1;
else return 0;
}
}
int main()
{
int V = 5,v;
struct Graph* graph = createGraph(V);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
v=bfs(graph,0,2);
if(v==1) printf("Yes");
else printf("No");
}