数据的结构：
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....）：
");
在输入无向图邻接矩阵相连的边信息时提示printf("请输入无向图邻接矩阵相连的边信息，相连标记为1
");
*/
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(); // 获取 '
' ，防止其对之后的字符输入造成影响;
printf("请输入无向图顶点信息（如ABCDEF....）：
");
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
");
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....）：
");
在输入无向图邻接矩阵相连的边信息时提示printf("请输入无向图邻接矩阵相连的边信息，相连标记为1
");
*/
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(); // 获取 '
' ，防止其对之后的字符输入造成影响;
printf("请输入无向图顶点信息（如ABCDEF....）：
");
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
");
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的结果为：
");
队首顶点出队，并赋值给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("创建邻接矩阵无向图并进行广度遍历
");
printf("请输入构造的无向图的顶点数和边数：
"); //输入顶点数和边数；
Martrix_Graph G; //申请一个图的空间;
Create_non_direction_martrix_Graph(&G); //创建图;
BFS_Travel(G);
return 0;
}
