#include <stdio.h> #define MAXVEX 100 /* 最大顶点数由用户定义 */ typedef char VertexType; /* 顶点类型应由用户定义 */ typedef int EdgeType; /* 边上的权值类型应由用户定义 */ typedef struct { VertexType vexs[MAXVEX]; EdgeType arc[MAXVEX][MAXVEX]; int numNodes; int numEdges; } AMGraph; int visited[MAXVEX]; //设置一个全局数组表示图中的顶点是否已经访问过，0号单元不表示有效数字 void BFS(AMGraph G, int v); void CreateGraph(AMGraph &G) { /*该函数平台已提供*/ } int main(void) { AMGraph G; scanf("%d %d",&G.numNodes,&G.numEdges); CreateGraph(G); BFS(G,1); // 从编号为1的顶点开始进行广度优先搜索 return 0; } /*仅提供以下代码*/ void BFS(AMGraph G, int v) { } 输入 第1行输入两个整数，分别表示图中的顶点数n和边数m 第2-m+1行每行输入两个整数i和j，分别表示编号为i的顶点和编号为j（编号从1开始）的顶点之间有一条边 输出 共1行信息有n个整数，表示广度优先搜索该图得到的序列，序列之间用一个空格隔开 样例输入 复制 8 9 1 2 1 3 2 4 2 5 3 6 3 7 4 8 5 8 6 7 样例输出 复制 1 2 3 4 5 6 7 8

下面是 BFS 函数的实现，注释中有详细说明。

void BFS(AMGraph G, int v) {
    int queue[MAXVEX];  // 定义一个队列，用于存放待访问的顶点
    int front = 0, rear = 0; // 队列的头尾指针，初始时队列为空
    int i, j, k;
    printf("%d ", v); // 访问起点 v 并输出
    visited[v] = 1; // 标记起点已经访问过
    queue[rear++] = v; // 将起点入队

    while (front != rear) { // 当队列不为空时循环
        i = queue[front++]; // 取出队头元素并出队
        for (j = 1; j <= G.numNodes; j++) { // 遍历与 i 相邻的所有顶点
            if (G.arc[i][j] == 1 && visited[j] == 0) { // 如果 j 是 i 的邻接点且未被访问过
                printf("%d ", j); // 访问 j 并输出
                visited[j] = 1; // 标记 j 已经访问过
                queue[rear++] = j; // 将 j 入队
            }
        }
    }
}

在主函数中调用 BFS 函数即可输出广度优先搜索的结果。

相关问题

优化这段代码#include<stdio.h> #include<stdlib.h> #include<malloc.h> #include<conio.h> #define OK 1 #define error 0 #define MVNum 100 #define MAXSIZE 10 typedef int OtherInfo,QElemtype; typedef char VerTexType; //结构体定义 typedef struct ArcNode{ int adjvex;

首先，该段代码中包含了一些不必要的头文件，例如：conio.h，malloc.h等。建议只保留stdio.h和stdlib.h。

其次，可以将#define OK 1和#define error 0替换为枚举类型，使代码更加清晰易读。

最后，在结构体定义中，可以将OtherInfo和QElemtype合并为一个类型，避免定义过多类型。同时，也可以将结构体中的变量类型进行优化，例如将int类型的adjvex改为short或者char类型。

重构后的代码如下所示：

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

#define MAX_VERTEX_NUM 100
#define MAX_ARC_NUM 10

typedef enum {
    ERROR = 0,
    OK = 1
} Status;

typedef char VertexType;
typedef int ArcType;

typedef struct ArcNode {
    int adjvex;
    struct ArcNode* nextarc;
    ArcType* info;
} ArcNode;

typedef struct VNode {
    VertexType data;
    ArcNode* firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {
    AdjList vertices;
    int vexnum, arcnum;
} ALGraph;

希望可以帮到你。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <malloc.h> #define MAXV 1000 #define ElemType int #define INF 32767typedef struct { int no; int info; }VertexType; typedef struct{ int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV]; }

MGraph;

void CreateMGraph(MGraph *G)
{
int i,j,k,w;
printf("请输入顶点数和边数：\n");
scanf("%d,%d",&(G->n),&(G->e));
for(i=0;i<G->n;i++)
{
printf("请输入第%d个顶点的编号和信息：\n",i+1);
scanf("%d,%d",&(G->vexs[i].no),&(G->vexs[i].info));
}
for(i=0;i<G->n;i++)
for(j=0;j<G->n;j++)
G->edges[i][j]=INF;
for(k=0;k<G->e;k++)
{
printf("请输入一条边的起点、终点和权值：\n");
scanf("%d,%d,%d",&i,&j,&w);
G->edges[i][j]=w;
G->edges[j][i]=w;
}
}

void ShortestPath_Dijkstra(MGraph G,int v0,int *D,int *P)
{
int final[MAXV];
int i,j,k,min;
for(i=0;i<G.n;i++)
{
final[i]=0;
D[i]=G.edges[v0][i];
P[i]=0;
}
D[v0]=0;
final[v0]=1;
for(i=1;i<G.n;i++)
{
min=INF;
for(j=0;j<G.n;j++)
if(!final[j]&&D[j]<min)
{
k=j;
min=D[j];
}
final[k]=1;
for(j=0;j<G.n;j++)
if(!final[j] && (min+G.edges[k][j]<D[j]))
{
D[j]=min+G.edges[k][j];
P[j]=k;
}
}
}

void DisplayResult(MGraph G,int v0,int *D,int *P)
{
int i,j,k;
printf("起点为%d的最短路径如下：\n",v0);
for(i=0;i<G.n;i++)
{
if(i!=v0)
{
printf("从%d到%d的最短路径长度为：%d，路径为：",v0,i,D[i]);
j=i;
while(P[j]!=0)
{
printf("%d<-",G.vexs[j].no);
j=P[j];
}
printf("%d\n",G.vexs[j].no);
}
}
}

int main()
{
MGraph G;
int v0=0;
int D[MAXV],P[MAXV];
CreateMGraph(&G);
ShortestPath_Dijkstra(G,v0,D,P);
DisplayResult(G,v0,D,P);
return 0;
}