在数据结构教程里，有一章是实现广度优先遍历非联通图，然后把遍历的图的节点
存在树的结构里，树的储存方式是孩子兄弟表示法。当我运行代码后，输入
了图的节点和节点之间的关系：
13,13
1
2
3
4
5
6
7
8
9
10
11
12
13
1,2
1,3
1,6
1,12
2,13
4,5
7,8
7,10
7,9
8,10
11,12
11,13
12,13
该有的结果应该是：
1 2 13 3 6 12 11 4 5 7 8 9 10
可我运行的结果是123 \n 456，也就是说function BFSForest根本没有被执行。
哪位大神可以帮我看看问题出在哪，谢谢！
以下是我的代码。
#include <stdio.h>
#include <stdlib.h>
#define MAX_VER_NUM 20 //图的最大节点数
#define VRTYPE int //弧的类型
#define VertexType int //节点类型
typedef enum {false,true} bool;
bool visited[MAX_VER_NUM];
typedef struct
{
VRTYPE adj;
}adjMatrix[MAX_VER_NUM][MAX_VER_NUM];//图的邻接矩阵
typedef struct
{
VertexType ver[MAX_VER_NUM];
adjMatrix arcs;
int num_vex,num_arcs;
}MGraph;//图的结构体
typedef struct
{
VertexType data;
struct gNode* lchild;
struct gNode* nextsibling;
}gNode;//生成树的节点，用孩子兄弟表示法
typedef struct
{
struct QueueCell *next;
gNode *node;
}QueueCell;//队列的节点
typedef struct
{
QueueCell *top;
QueueCell *tail;
}Queue;//定义队列的结构体
void initQueue(Queue **q)
{
if(!*q)
{
*q=(Queue*)malloc(sizeof(Queue));
(*q)->top=(QueueCell*)malloc(sizeof(QueueCell));
(*q)->top->next=NULL;
(*q)->top->node=NULL;
(*q)->tail=(*q)->top;//空队列头和尾巴在一起
}
}
int isEmpty(Queue *q)
{
if(q->tail==q->top)//空队列头和尾巴在一起
{
return 1;
}
return 0;//如果判定结果为错，必须返回0，而不能是-1
}
void EnQueue(Queue **q,gNode *g)
{
if(isEmpty(*q))//当队列为空时，头指针的next指针指向进队的节点
{
QueueCell *c=(*q)->top->next;
c->node=g;
(*q)->tail=c;
}
else//如果队列不为空，头指针不变，更新尾巴
{
QueueCell *c=(*q)->tail->next;
c->node=g;
(*q)->tail=c;
}
}
gNode* DeQueue(Queue **q)
{
QueueCell *c=(*q)->top->next;
(*q)->top->next= c->next;
if(!(c->next))//出队后，队列为空时，尾巴重新指向头结点
{
(*q)->tail=(*q)->top;
}
return c->node;
}
int locateVex(MGraph *G,VertexType v)
{
for(int i=0;i<G->num_vex;i++)
{
if(G->ver[i]==v)
{
return i;
}
}
return -1;
}
void createGraph(MGraph *G)
{
scanf("%d,%d",&(G->num_vex),&(G->num_arcs));//输入图的节点数和弧的数量
for(int i=0;i<G->num_vex;i++)
{
scanf("%d",&(G->ver[i]));//输入图每个节点的值
}
for(int i=0;i<G->num_vex;i++)//初始化邻接矩阵
{
for(int j=0;j<G->num_vex;j++)
{
G->arcs[i][j].adj=0;
}
}
for(int i=0;i<G->num_arcs;i++)//更新邻接矩阵
{
VertexType v1,v2;
scanf("%d,%d",&v1,&v2);
int n1=locateVex(G,v1);
int n2=locateVex(G,v2);
if(n1==-1||n2==-1)
{
printf("no such vertex");
exit(-1);
}
G->arcs[n1][n2].adj=1;
G->arcs[n2][n1].adj=1;
}
}
int firstAdjVex(MGraph *G,int v)//找到指定节点第一个相邻节点
{
for(int i=0;i<G->num_vex;i++)
{
if(G->arcs[v][i].adj)
{
return i;
}
}
return -1;
}
int nextAdjVex(MGraph *G, int v,int w)//找到指定节点下一个相邻节点
{
for(int i=w+1;i<G->num_vex;i++)
{
if(G->arcs[v][i].adj)
{
return i;
}dang
}
return -1;
}
void visit(gNode *g)
{
printf("%d ",g->data);
}
void BFSTree(MGraph *G,gNode **g)
{
printf("BFSTree");
gNode *node=NULL;
Queue *q=NULL;
initQueue(&q);
EnQueue(&q,*g);
int p=locateVex(G,(*g)->data);
visited[p]=true;
while(!isEmpty(q))
{
bool first =true;
gNode* n=DeQueue(&q);
node=n;
int v=locateVex(G,node->data);
for(int i=firstAdjVex(G,v);i>=0;i=nextAdjVex(G,v,i))
{
if(!visited[i])
{
gNode *gnode=(gNode*)malloc(sizeof(gNode));
gnode->data=G->ver[i];
gnode->lchild=NULL;
gnode->nextsibling=NULL;
visited[i]=true;
EnQueue(&q,gnode);
if(first)
{
node->lchild=gnode;
first=false;
}
else
{
node->nextsibling=gnode;
}
node=gnode;
}
}
}
}
void BFSForest(MGraph *G,gNode **g)
{
(*g)=NULL;
for(int i=0;i<G->num_vex;i++)
{
visited[i]=false;
}dang
gNode *node=NULL;
int v = locateVex(G,(*g)->data);
visited[v]=true;
for(int i=0;i<G->num_vex;i++)
{
if(!visited[i])
{
gNode *n=(gNode*)malloc(sizeof(gNode));
n->data=G->ver[i];
n->lchild=NULL;
n->nextsibling=NULL;
if(!(*g))
{
*g=n;
}
else
{
node->nextsibling=n;dang
}
node=n;
BFSTree(G,&n);
}
}
}
void preOrderTraverse(gNode *g)
{
visit(g);
preOrderTraverse(g->lchild);
preOrderTraverse(g->nextsibling);
}
int main(void)
{
MGraph G;
createGraph(&G);
printf("123\n");
gNode *g;
printf("456\n");
BFSForest(&G,&g);
printf("789\n");
preOrderTraverse(g);
return 0;
}
