Click here to Skip to main content
14,666,474 members
Rate this:
Please Sign up or sign in to vote.
See more:
#include <stdio.h>
#include <stdlib.h>
#include<conio.h>


struct AdjListNode
{
	int dest;
	struct AdjListNode* next;
};

struct AdjList
{
	struct AdjListNode *head;
};



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,*head1,*temp,*temp1;
	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=head1;
			head1=temp;}

			pCrawl=pCrawl->next;

		}
		temp=head1;
		while(temp!=NULL)
		{
			temp1=temp;
			temp=temp->next;
		}

		s=temp1->dest;
		free(temp);
		temp1->next=NULL;
	}
	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");

}


What I have tried:

I tried to search a path in an undirected graph. My code found successful while searching an edge only.

Input:
graph,0,1
graph,0,2

Output:
Yes
..............

Expected output:
Yes
Yes

The first output was same as expected output because it was an edge while the next wasn't an edge.
Posted
Updated 5-May-16 21:55pm
v5
Comments
Patrice T 5-May-16 4:45am
   
What is interesting in this code is that the word "Yes" is not in this code !
Member 12378355we 5-May-16 4:49am
   
Now.? Whats the problem with the bfs function?

Rate this:
Please Sign up or sign in to vote.

Solution 1

You should learn to use the debugger as soon as possible. Rather than guessing what your code is doing, It is time to see your code executing and ensuring that it does what you expect.

The debugger allow you to follow the execution line by line, inspect variables and you will see that there is a point where it stop doing what you expect.
Debugger - Wikipedia, the free encyclopedia[^]
Mastering Debugging in Visual Studio 2010 - A Beginner's Guide[^]

Try to give a code example that contain the word "Yes".
Using indentation is considered an help to read code.

[Update]
The main problem with your code is that it can not say "Yes" 2 times.
   
v2
Comments
Member 12378355we 6-May-16 3:58am
   
Not at all.
Rate this:
Please Sign up or sign in to vote.

Solution 2

#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");
}
   
v4

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 503-250 Ferrand Drive Toronto Ontario, M3C 3G8 Canada +1 416-849-8900 x 100