weixin_45994861 2020-05-25 20:11 采纳率: 50%
浏览 178

图的BFS遍历的输出问题

正确的输入输出:

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的输出中, 前三个输出相同
A B F 第四个标准答案为 C 但在此时的 B 出队对应的第一个入队的元素为 号元素 G; 是我的代码有问题还是答案有问题?


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

  • 写回答

1条回答 默认 最新

  • 关注
    评论

报告相同问题?

悬赏问题

  • ¥15 矩阵加法的规则是两个矩阵中对应位置的数的绝对值进行加和
  • ¥15 活动选择题。最多可以参加几个项目?
  • ¥15 飞机曲面部件如机翼,壁板等具体的孔位模型
  • ¥15 vs2019中数据导出问题
  • ¥20 云服务Linux系统TCP-MSS值修改?
  • ¥20 关于#单片机#的问题:项目:使用模拟iic与ov2640通讯环境:F407问题:读取的ID号总是0xff,自己调了调发现在读从机数据时,SDA线上并未有信号变化(语言-c语言)
  • ¥20 怎么在stm32门禁成品上增加查询记录功能
  • ¥15 Source insight编写代码后使用CCS5.2版本import之后,代码跳到注释行里面
  • ¥50 NT4.0系统 STOP:0X0000007B
  • ¥15 想问一下stata17中这段代码哪里有问题呀