图的遍历c语言ABCDEFGH
时间: 2023-12-11 08:32:57 浏览: 29
以下是使用邻接矩阵实现的图的广度优先遍历的C语言代码,其中ABCDEFGH表示图的顶点:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100
#define TRUE 1
#define FALSE 0
#define INFINITY 65535
typedef struct {
int arcs[MAXVEX][MAXVEX];
int numVex, numEdg;
} MGraph;
typedef struct {
int data[MAXVEX];
int front, rear;
} Queue;
void CreateMGraph(MGraph *g) {
int i, j, k, w;
printf("请输入顶点数和边数:");
scanf("%d %d", &g->numVex, &g->numEdg);
for (i = 0; i < g->numVex; i++) {
for (j = 0; j < g->numVex; j++) {
g->arcs[i][j] = INFINITY;
}
}
for (k = 0; k < g->numEdg; k++) {
printf("请输入边(vi, vj)的下标i, j和权值w:");
scanf("%d %d %d", &i, &j, &w);
g->arcs[i][j] = w;
g->arcs[j][i] = w;
}
}
void InitQueue(Queue *q) {
q->front = q->rear = 0;
}
int QueueEmpty(Queue *q) {
if (q->front == q->rear) {
return TRUE;
} else {
return FALSE;
}
}
void EnQueue(Queue *q, int e) {
q->data[q->rear] = e;
q->rear++;
}
int DeQueue(Queue *q) {
int e;
e = q->data[q->front];
q->front++;
return e;
}
void BFSTraverse(MGraph g, int v) {
int i, j;
Queue q;
int visited[MAXVEX];
for (i = 0; i < g.numVex; i++) {
visited[i] = FALSE;
}
InitQueue(&q);
visited[v] = TRUE;
printf("%c ", v + 'A');
EnQueue(&q, v);
while (!QueueEmpty(&q)) {
i = DeQueue(&q);
for (j = 0; j < g.numVex; j++) {
if (g.arcs[i][j] != INFINITY && !visited[j]) {
visited[j] = TRUE;
printf("%c ", j + 'A');
EnQueue(&q, j);
}
}
}
}
int main() {
MGraph g;
CreateMGraph(&g);
printf("广度优先遍历结果为:");
BFSTraverse(g, 0);
printf("\n");
return 0;
}
```