#2
azzbcc2015-11-30 18:40
|
只有本站会员才能查看附件,请 登录
只有本站会员才能查看附件,请 登录
六度空间,用邻接矩阵做的,看了两个小时还没找到错在哪,按照视频上的方法做的,代码找不到错误位置啊。
程序代码:
#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 ;
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);
// }
}
#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 ;
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);
// }
}
只有本站会员才能查看附件,请 登录
只有本站会员才能查看附件,请 登录