Click here to Skip to main content
15,892,059 members
Please Sign up or sign in to vote.
1.00/5 (1 vote)
See more:
C++
#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?

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.
 
Share this answer
 
v2
Comments
Member 12378355we 6-May-16 3:58am    
Not at all.
C++
#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");
}
 
Share this answer
 
v4

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



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900