以下代码在其BFS函数中出错

问题描述

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

}

我的尝试：



我试图在无向图中搜索路径。我的代码在搜索边缘时发现成功。



输入：

图，0,1

图，0,2



输出：

是

........... ...



预期产量：

是

是



第一个输出与预期输出相同，因为它是边缘而下一个不是边缘。

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.

推荐答案

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

这篇关于以下代码在其BFS函数中出错的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！