c语言图的邻接矩阵BFS 遍历的输出问题;

Question

数据的结构：

int visit[MAX_VERTEX];   //标记顶点是否被访问

/**图的邻接矩阵的建立**/
typedef struct Martrix_Graph
{
    char vertex[MAX_VERTEX]; //存储顶点信息
    int edge[MAX_VERTEX][MAX_VERTEX]; //存储边信息
    int vertex_number, edge_number;//存储顶点数和边数
}Martrix_Graph;

/**BFS会用到队列这个数据结构**/
/**循环队列**/

typedef struct
{
    char data[MAX_VERTEX]; //存储信息;
    int front;  //头指针
    int rear;   //尾指针，队列非空则指向队尾最后一个元素后一个位置 
}SqQueue;

---

邻接矩阵的函数：

/*
TODO:以邻接矩阵为存储结构建立无向图
功能描述：创建以邻接矩阵为存储结构的无向图
参数描述：Martrix_Graph型指针G为主要操作参数
提示：在输入无向图顶点信息时提示printf("请输入无向图顶点信息（如ABCDEF....）：\n");
      在输入无向图邻接矩阵相连的边信息时提示printf("请输入无向图邻接矩阵相连的边信息，相连标记为1\n");
*/
void Create_non_direction_martrix_Graph(Martrix_Graph *G)
{
    int  i, k, j ,number;
    scanf_s("%d", &G->vertex_number);   //输入顶点的数目，和边的总数;

    scanf_s("%d", &G->edge_number); 
    getchar();   // 获取 '\n' ，防止其对之后的字符输入造成影响;
    printf("请输入无向图顶点信息（如ABCDEF....）：\n");
    for (i = 0; i < G->vertex_number; i++)
        scanf_s("%c", &G->vertex[i]);    // 输入顶点的信息;
    // 初始化邻阶矩阵
    for (i = 0; i < G->edge_number; i++)
        for (j = 0; j < G->edge_number; j++)
            G->edge[i][j] = 0;  
        
    printf("请输入无向图邻接矩阵相连的边信息，相连标记为1\n");
    for (k = 0; k < G->edge_number; k++)
    {
        getchar();
        scanf_s("%d %d %d", &i, &j, &number);
        G->edge[i][j] = number;
    }

}

---

图的BFS函数:

void BFS_Travel(Martrix_Graph G)  //为变量;
{
    SqQueue queue; 
    int i, j ,w;
    char data ,e;
    // 初始化;
    memset(visit, 0, MAX_VERTEX);
    InitQueue(&queue);
    // bfs 输出;
    for (i = 0; i < G.vertex_number; i++)
    {
        if (visit[i] == 0)
        {
            visit[i] = 1;
            data = G.vertex[i];
            printf("%c ", data); //输出遍历;
            EnQueue(&queue, data);
            while ( !isEmptyQueue(&queue))    //当队列不为空时;
            {
                       // 取出队首元素找到它的对应位置;
                DeQueue(&queue, &e);         //通过e带出元素;
                w = LocateVex(&G, e);
                       //取出与该元素相连接的元素;
                for (j = 0; j < G.vertex_number; j++)
                {
                        //当未访问和有为该元素的连接元素时;
                    if (visit[j] == 0 && G.edge[w][j] == 1)
                    {
                        visit[j] = 1;
                        data = G.vertex[j];
                        printf("%c ", data);
                        EnQueue(&queue, data);
                     }
                }

            }
        }
    }


}

---

队列相关的函数

//队列初始化
void InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
}
//入队
bool EnQueue(SqQueue *Q, char e)
{
    //采用留一个空间的方式;
   //判断队列是否满
    if ((Q->rear + 1) % MAX_VERTEX == Q->front)
        return false;

    Q->data[Q->rear] = e;
    //队尾移动;
    Q->rear = (Q->rear + 1) % MAX_VERTEX;
    return true;
}
//出队---删除队首元素，并赋给e

void  DeQueue(SqQueue *Q, char *e)   // 在此BFS中可不考虑为空；
{

        *e = Q->data[Q->front];  //取出元素；
        //将对应的位置++；
       Q->front = (Q->front + 1) % MAX_VERTEX;


}
//队列判空
bool isEmptyQueue(SqQueue *Q) 
{

    return Q->front == Q->rear ? true : false;   //返回 0 1；
}

---

元素定位函数:

int LocateVex(Martrix_Graph *G, char v)
{
    int i;
    for (i = 0; i < G->vertex_number; i++) {
        if (G->vertex[i] == v)
            break;
    }
    return i;

}

---

标准输入输出
9
15
ABCDEFGHI
0 1 1
0 5 1
1 6 1
5 6 1
2 1 1
1 8 1
2 8 1
6 7 1
2 3 1
3 8 1
3 7 1
3 4 1
4 7 1
4 5 1
3 6 1
A B F C G I E D H
我的输出：

经过单步调试矩阵的发现输入没有问题，主要的问题应该在BFS遍历函数中；
Question :

输出不正确:前三个输出相同: 为 A B F 此时的 与 A 相连的元素已经全部入队列 A 已经出队列 ；下一步B出队列 ；与B相连的

1 6 1
1 8 1
这两个元素入队列 分别为 G 和 I；
请问 c是如何在F 之后的 是我BFS 的遍历函数不正确，还是它的标准答案有问题？求大神解惑；

完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include<string.h>

#define MAX_VERTEX 10
//无边界时的值;
#define inf 65535  //表示两点之间没有边相连
//访问标识函数；
int visit[MAX_VERTEX];   //标记顶点是否被访问

/**图的邻接矩阵的建立**/
//邻接矩阵数据结构定义
typedef struct Martrix_Graph
{
    char vertex[MAX_VERTEX]; //存储顶点信息
    int edge[MAX_VERTEX][MAX_VERTEX]; //存储边信息
    int vertex_number, edge_number;//存储顶点数和边数
}Martrix_Graph;

/**BFS会用到队列这个数据结构**/
/**循环队列**/

typedef struct
{
    char data[MAX_VERTEX]; //存储信息;
    int front;  //头指针
    int rear;   //尾指针，队列非空则指向队尾最后一个元素后一个位置
}SqQueue;

/*
TODO:以邻接矩阵为存储结构建立无向图
功能描述：创建以邻接矩阵为存储结构的无向图
参数描述：Martrix_Graph型指针G为主要操作参数
提示：在输入无向图顶点信息时提示printf("请输入无向图顶点信息（如ABCDEF....）：\n");
      在输入无向图邻接矩阵相连的边信息时提示printf("请输入无向图邻接矩阵相连的边信息，相连标记为1\n");
*/
void Create_non_direction_martrix_Graph(Martrix_Graph *G)
{
    int  i, k, j ,number;
    scanf_s("%d", &G->vertex_number);   //输入顶点的数目，和边的总数;

    scanf_s("%d", &G->edge_number); 
    getchar();   // 获取 '\n' ，防止其对之后的字符输入造成影响;
    printf("请输入无向图顶点信息（如ABCDEF....）：\n");
    for (i = 0; i < G->vertex_number; i++)
        scanf_s("%c", &G->vertex[i]);    // 输入顶点的信息;
    // 初始化邻阶矩阵
    /*for (i = 0; i < G->edge_number; i++)
        for (j = 0; j < G->edge_number; j++)
            G->edge[i][j] = 0;  
            */ 

    printf("请输入无向图邻接矩阵相连的边信息，相连标记为1\n");
    for (k = 0; k < G->edge_number; k++)
    {
        getchar();
        scanf_s("%d %d %d", &i, &j, &number);
        G->edge[i][j] = number;
    }

}


//队列初始化
void InitQueue(SqQueue *Q)
{
    Q->front = 0;
    Q->rear = 0;
}
//入队
bool EnQueue(SqQueue *Q, char e)
{
    //采用留一个空间的方式;
   //判断队列是否满
    if ((Q->rear + 1) % MAX_VERTEX == Q->front)
        return false;

    Q->data[Q->rear] = e;
    //队尾移动;
    Q->rear = (Q->rear + 1) % MAX_VERTEX;
    return true;
}
//出队---删除队首元素，并赋给e

void  DeQueue(SqQueue *Q, char *e)   //e 也为 char 型的指针;
{

        *e = Q->data[Q->front];  //取出元素；
        //将对应的位置++；
       Q->front = (Q->front + 1) % MAX_VERTEX;


}
//队列判空
bool isEmptyQueue(SqQueue *Q)
{

    return Q->front == Q->rear ? true : false;   //返回 0 1；
}

/*找到顶点v的对应下标*/
int LocateVex(Martrix_Graph *G, char v)
{
    int i;
    for (i = 0; i < G->vertex_number; i++) {
        if (G->vertex[i] == v)
            break;
    }
    return i;

}
/*
TODO:对整个图进行广度优先遍历
功能描述：对整张无向图进行广度优先遍历
参数描述：Martrix_Graph型参数G
提示：遍历图的顶点时提示printf("此邻接矩阵无向图BFS的结果为：\n");
      队首顶点出队，并赋值给data时输出printf("%c ",data);
*/

void BFS_Travel(Martrix_Graph G)  //为变量;
{
    SqQueue queue; 
    int i, j ,w;
    char data ,e;
    // 初始化;
    memset(visit, 0, MAX_VERTEX);
    InitQueue(&queue);
    // bfs 输出;
    for (i = 0; i < G.vertex_number; i++)
    {
        if (visit[i] == 0)
        {
            visit[i] = 1;
            data = G.vertex[i];
            printf("%c ", data); //输出遍历;
            EnQueue(&queue, data);
            while ( !isEmptyQueue(&queue))    //当队列不为空时;
            {
                       // 取出队首元素找到它的对应位置;
                DeQueue(&queue, &e);         //通过e带出元素;
                w = LocateVex(&G, e);
                       //取出与该元素相连接的元素;
                for (j = 0; j < G.vertex_number; j++)
                {
                        //当未访问和有为该元素的连接元素时;
                    if (visit[j] == 0 && G.edge[w][j] == 1)
                    {
                        visit[j] = 1;
                        data = G.vertex[j];
                        printf("%c ", data);
                        EnQueue(&queue, data);
                     }
                }

            }
        }
    }


}

int main()
{
    printf("创建邻接矩阵无向图并进行广度遍历\n");
    printf("请输入构造的无向图的顶点数和边数：\n");  //输入顶点数和边数；
    Martrix_Graph  G;      //申请一个图的空间;
    Create_non_direction_martrix_Graph(&G); //创建图;
    BFS_Travel(G);
    return 0;
}