广度优先搜索树 非连通图的遍历

在数据结构教程里,有一章是实现广度优先遍历非联通图,然后把遍历的图的节点
存在树的结构里,树的储存方式是孩子兄弟表示法。当我运行代码后,输入
了图的节点和节点之间的关系:

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;
}

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!
立即提问