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

数据的结构：

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 的遍历函数不正确，还是它的标准答案有问题？求大神解惑；

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

全站热榜