c语言设计算法实现图的广度优先遍历

以下是通过C语言实现的图的广度优先遍历算法：

#define MAX 100 //定义最大顶点数
typedef struct ArcNode //边结点
{
    int adjvex; //邻接点在数组中的位置下标
    struct ArcNode *nextarc; //指向下一个邻接点的指针
}ArcNode;

typedef struct VertexNode //顶点结点
{
    char data; //顶点信息
    ArcNode *firstarc; //指向第一个邻接点的指针
}VertexNode, AdjList[MAX];

typedef struct //邻接表
{
    AdjList adjlist;
    int n, e; //顶点数和边数
}AdjGraph;

int visited[MAX] = {0}; //全局数组，标记顶点是否被访问过

//广度优先遍历算法
void BFS(AdjGraph *G, int v)
{
    int queue[MAX], front = 0, rear = 0; //定义队列
    ArcNode *p;
    printf("%c ", G->adjlist[v].data); //输出被访问顶点的信息
    visited[v] = 1; //标记该顶点已被访问
    rear = (rear + 1) % MAX; //入队
    queue[rear] = v;
    while (front != rear) //队列不为空时循环
    {
        front = (front + 1) % MAX; //出队
        v = queue[front];
        p = G->adjlist[v].firstarc;
        while (p != NULL) //遍历该顶点的所有邻接点
        {
            if (visited[p->adjvex] == 0) //若该邻接点未被访问
            {
                printf("%c ", G->adjlist[p->adjvex].data); //输出被访问顶点的信息
                visited[p->adjvex] = 1; //标记该顶点已被访问
                rear = (rear + 1) % MAX; //入队
                queue[rear] = p->adjvex;
            }
            p = p->nextarc;
        }
    }
}