#include <stdio.h> #include <stdlib.h> #define MAX_VERTEX_NUM 50 typedef struct { int data[MAX_VERTEX_NUM]; int front, rear; } Queue; void InitQueue(Queue *Q) { Q->front = Q->rear = 0; } int QueueEmpty(Queue Q) { return Q.front == Q.rear; } void EnQueue(Queue *Q, int x) { Q->data[Q->rear++] = x; } int DeQueue(Queue *Q) { return Q->data[Q->front++]; } typedef struct { int vex[MAX_VERTEX_NUM]; int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; int vexnum, edgenum; } Graph; void CreateGraph(Graph *G) { int i, j; scanf("%d", &G->vexnum); for (i = 0; i < G->vexnum; i++) { for (j = 0; j < G->vexnum; j++) { scanf("%d", &G->edge[i][j]); } } } int FirstAdjVex(Graph G, int v) { int i; for (i = 0; i < G.vexnum; i++) { if (G.edge[v][i] == 1) { return i; } } return -1; } int NextAdjVex(Graph G, int v, int w) { int i; for (i = w + 1; i < G.vexnum; i++) { if (G.edge[v][i] == 1) { return i; } } return -1; } void BFS(Graph G, int v, int visited[]) { Queue Q; int w, i; InitQueue(&Q); visited[v] = 1; printf("%d ", v); EnQueue(&Q, v); while (!QueueEmpty(Q)) { w = DeQueue(&Q); for (i = FirstAdjVex(G, w); i != -1; i = NextAdjVex(G, w, i)) { if (!visited[i]) { visited[i] = 1; printf("%d ", i); EnQueue(&Q, i); } } } } void BFSTraverse(Graph G) { int visited[MAX_VERTEX_NUM] = {0}; int i; for (i = 0; i < G.vexnum; i++) { if (!visited[i]) { BFS(G, i, visited); } } } int main() { Graph G; CreateGraph(&G); BFSTraverse(G); printf("\n"); return 0; }上述代码的各个步骤都有什么用

这段代码是一个实现图的广度优先遍历算法的程序。下面是各个步骤的作用：

1. 定义队列结构体Queue，包含队列元素data和队首front、队尾rear指针。

2. 初始化队列操作InitQueue，将队首和队尾指针都初始化为0，表示队列为空。

3. 判断队列是否为空操作QueueEmpty，如果队首指针等于队尾指针，则队列为空。

4. 入队操作EnQueue，将元素x添加到队尾rear指向的位置，并将rear指针加1。

5. 出队操作DeQueue，返回队首front指向的元素，并将front指针加1。

6. 定义图结构体Graph，包含顶点vex、边edge、顶点数vexnum和边数edgenum。

7. 创建图操作CreateGraph，输入图的顶点数vexnum和邻接矩阵edge，存储在Graph结构体中。

8. 查找顶点v的第一个邻接顶点操作FirstAdjVex，从v的第一个邻接顶点开始遍历邻接矩阵edge，返回第一个邻接顶点的位置。

9. 查找顶点v的下一个邻接顶点操作NextAdjVex，从w+1开始遍历邻接矩阵edge，返回下一个邻接顶点的位置。

10. 广度优先遍历操作BFS，从顶点v开始遍历图，使用队列实现遍历过程，访问每个未被访问的邻接顶点，将其放入队列中。

11. 广度优先遍历操作BFSTraverse，对整个图进行广度优先遍历，使用visited数组记录每个顶点是否已被访问。

12. 主函数main，创建图G并进行广度优先遍历。

相关问题

优化这段代码#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;
}