输出无向图的给定起点的先广序列。
输入格式:
输入第一行给出三个正整数，分别表示无向图的节点数N（1<N≤10）、边数M（≤50）和探索起始节点编号S（节点从1到N编号）。
随后的M行对应M条边，每行给出一对正整数，分别是该条边直接连通的两个节点的编号。
输出格式:
输出从S开始的无向图的先广搜索序列，用一个空格隔开，最后也有一个空格；如果为非连通图，再在结尾处另起一行输出一个0，表示此图非连通。
由于广度优先遍历的节点序列是不唯一的，为了使得输出具有唯一的结果，我们约定以表头插入法构造邻接表。
输入样例:
6 8 2
1 2
2 3
3 4
4 5
5 6
6 4
3 6
1 5
输出样列：
2 3 1 6 4 5
我的代码如下：
#include<iostream>
#include<malloc.h>
using namespace std;
#define MAX 10
#define MAXQ 15
bool visited[10];
int cnt;
typedef struct ArcNode
{
int adjvex;
struct ArcNode *nextarc;
}ArcVNode;
typedef struct VNode
{
int data;
struct ArcNode *firstarc;
}VNode,AdjList[MAX];
typedef struct
{
AdjList vertices;
int vexnum,arcnum;
int startNode;
}ALGraph;
typedef struct Queue
{
int front,rear;
int *base;
}Queue;
Queue Q;
void InitQueue(Queue &Q)
{
Q.front=0;
Q.rear=0;
Q.base=(int *)malloc(MAXQ*sizeof(int));
}
void EnQueue(Queue &Q,int v)
{
Q.base[Q.rear]=v;
Q.rear=(Q.rear+1)%MAXQ;
}
void DeQueue(Queue &Q)
{
Q.front=(Q.front+1)%MAXQ;
}
void BFS(ALGraph &G,int vex)
{
InitQueue(Q);
EnQueue(Q,vex);
visited[vex]=true;
cout<<G.vertices[vex].data<<" ";
cnt++;
while(Q.front!=Q.rear)
{
vex=Q.base[Q.front];
DeQueue(Q);
for(ArcNode *s=G.vertices[vex].firstarc;s!=NULL;s=(*s).nextarc)
{
if(!visited[s->adjvex])
{
EnQueue(Q,s->adjvex);
visited[s->adjvex]=true;
cout<<G.vertices[s->adjvex].data<<" ";
cnt++;
}
}
}
}
void HeadInsert(ALGraph &G,int v1,int v2)
{
ArcNode *p,*q;
p=(ArcNode *)malloc(sizeof(ArcNode));
p->adjvex=v2;
if(!G.vertices[v1].firstarc)
{
G.vertices[v1].firstarc = p;
p->nextarc = NULL;
}
else
{
q=G.vertices[v1].firstarc;
p->nextarc=q;
G.vertices[v1].firstarc=p;
}
}
void create(ALGraph &G)
{
cin>>G.vexnum>>G.arcnum>>G.startNode;
for(int i=1;i<=G.vexnum;i++)
{
G.vertices[i].data=i;
G.vertices[i].firstarc=NULL;
}
for(int k=1;k<=G.vexnum;k++)
{
int v1,v2;
cin>>v1>>v2;
HeadInsert(G,v1,v2);
HeadInsert(G,v2,v1);
}
}
int main()
{
ALGraph G;
create(G);
BFS(G,G.startNode);
cout<<(cnt==G.vexnum ? "" : "\n0");
}
为什么在编译器运行的结果正确，拿到PTA提交代码，却显示输出结果错误？该怎么改正？
create() 方法里面，第2个循环是录入边，循环结束条件 k<=G.vexnum 应该是 k<=G.arcnum。改掉这个，你的代码就完美了