六度空间,错在哪了?

原题



#include <stdio.h>
#include <stdlib.h>

#define MaxSizeQ 10000
#define MaxVertex 10000

int Visited[MaxVertex] ;
typedef int VertexType ;
typedef int EdgeType   ;

typedef struct
{
	int rear ;
	int front ;
	int queue[MaxSizeQ] ;
}Queue ;


typedef struct
{
	VertexType vertex[MaxVertex] ;//顶点数组
	EdgeType edge[MaxVertex][MaxVertex] ;//边数组edge[v1][v2]v1,v2为顶点坐标而非顶点名称
	int n ;//顶点个数
	int e ;//边个数

}MGraph ;


void  InitializeQ( Queue* Q  ) //初始化队列
{
	Q->front=0 ;
	Q->rear=-1 ;
}

int IsFullQ( Queue* Q  )  //判断队列是否满
{
	if(Q->rear==MaxSizeQ) return 1;
	else return 0 ;
}


int IsEmptyQ( Queue* Q  )	//判断队列是否空
{
	//	printf("判断队列是否空\n");	
	if(Q->rear < Q->front )
		return 1 ;
	else return 0 ;																								
}


void AddQ( Queue* Q ,int CurV )	//顶点编号入队
{
	
	if( !(IsFullQ(Q)) )
	{ 
		Q->rear++ ;
		Q->queue[Q->rear ] = CurV ;		
	}
}


int  DeleteQ( Queue* Q ) //顶点坐标出队
{
	int i ;
	i = Q->front ;
	if( !( IsEmptyQ(Q) ) )
	{
		Q->front++ ;
		return Q->queue[i] ;//返回顶点坐标
	}
}


void CreateMGraph( MGraph* G )
{
	int i,j ;
	int v1,v2 ;

	scanf("%d",&G->n) ;//输入顶点个数
	scanf("%d",&G->e) ;//输入边个数
	

	for(i=0 ; i<G->n ; i++ )//顶点从1到N编号(命名)
		G->vertex[i] = i+1 ;
	for(i=0 ; i<G->n; i++ )//边初始化
		for(j=0 ; j<G->n ; j++ )
			G->edge[i][j] = 0 ;
	for(i=0 ; i<G->e ; i++)
	{
		scanf("%d %d",&v1,&v2);//输入顶点名称,比坐标大1(1到N)
		G->edge[v1-1][v2-1] = G->edge[v2-1][v1-1] = 1 ;
	}
}


int  BFS( MGraph* G, int CurV, Queue* Q )
{
	//CurV当前搜索结点坐标
	int i,V ;
	int VisitedCount ;
	int Level ;
	int  LastV , TailV ;//CurV当前搜索结点,当前结点所在层最后一个结点,下一层最后结点各自坐标

	AddQ( Q,CurV ) ;//当前结点坐标压入队中

	printf("入 队 节 点 坐 标  %d \n",CurV);

	Visited[CurV] = 1 ;
	VisitedCount = 1  ;
	LastV = CurV ;
	Level = 0 ;
	
	while( !(IsEmptyQ(Q)) ) 
	{
		printf("出 队 结 点 坐 标  %d \n" , DeleteQ( Q )) ;
		V = DeleteQ( Q ) ;
	
		for(i=0 ; i<G->n ; i++ )		
		{
			printf("V=%d ,i=%d , G->edge[V][i]=%d \n",V,i,G->edge[V][i] ) ;
			if(Visited[i] == 0 && G->edge[V][i]==1 )//如果i号顶点未被访问 且 当前顶点可到达到i顶点
			{
				printf("Visited[%d]= %d \n",i,Visited[i] ) ;
				printf("入 队 节 点 坐 标 %d \n",i);
				AddQ( Q,i ) ;//当前结点坐标压入队中
				Visited[i] = 1 ;
				VisitedCount ++ ;
				TailV = i ;
			}
		}

		if( LastV == V )
		{ Level++ ; LastV = TailV ; }

		if( Level == 6 )   break ;
		//	return VisitedCount ;
	}
	return VisitedCount ;
}




int main(   )
{
	int i,j ;
	int VisitedCount ;
	int CurV ;

	MGraph* G ;
	Queue*  Q ;

	Q = (Queue*)malloc( sizeof(Queue) ) ;
	G = (MGraph*)malloc( sizeof(MGraph) ) ;//图中顶点从1开始编号

	InitializeQ( Q ) ;
	CreateMGraph( G ) ;

	for(i=0 ; i<G->n; i++ )//输出矩阵
	{
		{	for(j=0 ; j<G->n ; j++ )
		printf( "%d "  , G->edge[i][j] ) ;	 }
		printf("\n") ;
	}


	for( CurV=0 ; CurV< G->n ; CurV++  )
	{	
		for( i=0 ; i<G->n ; i++)//标记数组初始化
			Visited[i]=0 ;

		VisitedCount = BFS(  G, 0 ,  Q ) ;

		printf("count=%d\n",VisitedCount);
	}
	
}

全部评论
来个人帮忙看看呗
点赞 回复 分享
发布于 2015-12-02 08:53
点赞 回复 分享
发布于 2015-12-02 22:43
用数组做吧,用结构体做太麻烦了
点赞 回复 分享
发布于 2015-12-03 10:52

相关推荐

不愿透露姓名的神秘牛友
09-30 20:11
点赞 评论 收藏
分享
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务