用C语言写一个图的广度优先遍历算法
时间: 2023-03-16 16:43:55 浏览: 145
我可以提供一些参考代码,这是一个广度优先遍历的C语言算法: #include <stdio.h>
#include <stdlib.h>
#define MAX 100 //队列结构
typedef struct Queue
{
int data[MAX];
int front, rear;
}Queue; //图结构
typedef struct Graph
{
int n;
int **e;
int *visited;
}Graph; //初始化队列
void InitQueue(Queue *Q)
{
Q->front = 0;
Q->rear = 0;
} //判断队列是否为空
int IsEmpty(Queue *Q)
{
if (Q->rear == Q->front)
return 1;
else
return 0;
} //入队
void EnQueue(Queue *Q, int x)
{
Q->data[Q->rear] = x;
Q->rear = (Q->rear + 1) % MAX;
} //出队
int DeQueue(Queue *Q)
{
int x;
x = Q->data[Q->front];
Q->front = (Q->front + 1) % MAX;
return x;
} //图的广度优先遍历算法
void BFS(Graph *G, int v)
{
int i;
Queue Q;
InitQueue(&Q);
G->visited[v] = 1;
printf("%d ", v);
EnQueue(&Q, v);
while (!IsEmpty(&Q))
{
v = DeQueue(&Q);
for (i = 0; i < G->n; i++)
{
if (G->e[v][i] == 1 && G->visited[i] == 0)
{
G->visited[i] = 1;
printf("%d ", i);
EnQueue(&Q, i);
}
}
}
} int main()
{
int i, j;
Graph G;
printf("请输入顶点数和边数:");
scanf("%d %d", &G.n, &j);
G.e = (int **)malloc(G.n * sizeof(int *));
for (i = 0; i < G.n; i++)
{
G.e[i] = (int *)malloc(G.n * sizeof(int));
}
G.visited = (int *)malloc(G.n * sizeof(int));
printf("请输入邻接矩阵:\n");
for (i = 0; i < G.n; i++)
{
for (j = 0; j < G.n; j++)
{
scanf("%d", &G.e[i][j]);
}
}
printf("从顶点0开始的广度优先遍历的结果是:\n");
BFS(&G, 0);
printf("\n");
return 0;
}
阅读全文
相关推荐


















