以下代码在其BFS函数中出错 [英] The following code got something wrong in its BFS function

问题描述

#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.

推荐答案

你应该学习使用调试器尽快。而不是猜测你的代码在做什么，现在是时候看到你的代码执行并确保它完成你期望的。



调试器允许你跟踪执行逐行检查变量，你会看到它有一个停止做你期望的点。

调试器 - 维基百科，免费的百科全书 [ ^ ]

掌握Visual Studio 2010中的调试 - A初学者指南 [ ^ ]



尝试给出一个包含单词Yes的代码示例。

使用缩进被认为是帮助阅读代码。



[更新]

您的代码的主要问题是它不能说是2次。

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.

#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函数中出错的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！