图的广度搜索,很简单,在VC++中运行正确,在acm网上测评上怎么会有这样的错误呢
#include <stdio.h>#define MAXSIZE 100
int visited[MAXSIZE]={0};//标记是否被访问过,0表示没有,1表示访问过
//队列的数据结构
typedef struct
{
int data[MAXSIZE];
int front;
int rear;
}squeue;
//图的数据结构
typedef struct
{
int no;//顶点编号
}vertexType;
typedef struct
{
int num,edg;//顶点数和边数
int edges[MAXSIZE][MAXSIZE];//存放边之间的值
vertexType vex[MAXSIZE];//存放顶点
}MGraph;//定义图
//入队
void enQueue(squeue &qu,int x)
{
qu.rear=(qu.rear+1)%MAXSIZE;
qu.data[qu.rear+1]=x;
}
//出队
int deQueue(squeue &qu)
{
if(qu.front==qu.rear) return 0;
else {
int x;
qu.front=(qu.front+1)%MAXSIZE;
x=qu.data[qu.front];
return x;
}
}
/*
定义bfs函数:
广度优先搜索遍历类似于树的按层次遍历的过程。其过程为:假设从图中的某顶点v出发,
在访问了v之后依次访问v的各个未曾被访问过的邻接点,然后分别从这些邻接点出发依次访问它们的邻接点,
并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问,直至图中所有已被访问的顶点的邻接点都被访问到。
若此时图中尚有顶点未被访问,则另选图中一个未曾被访问的顶点作为起始点。重复上述过程,直至图中所有顶点都被访问到为止。
*/
void bfs(MGraph G,int no,int n,int visited[])
{
squeue que;
que.front=0;
que.rear=0;
enQueue(que,no);
printf("%d ",no);//访问顶点,进行输出
visited[no]=1;//将其值置1
while(que.front!=que.rear){
deQueue(que);
int k=0;
for(k=0;k<n;k++)
{
if(G.edges[no][k]&&!visited[k]){
enQueue(que,k);
printf("%d ",k);//访问顶点,进行输出
visited[k]=1;//将其值置1
}
}
}
}
int main()
{
//读入数据
int n,i=0,j=0;
MGraph G;
scanf("%d",&n);
for(i=0;i<n;i++)
for(j=0;j<n;j++)
{
scanf("%d",&G.edges[i][j]);
}
for(i=0;i<n;i++)
{
if(!visited[i])
bfs(G,i,n,visited);
}
return 0;
}