BFS

​

把根结点放到队列的末尾

每次从队列的头部取出一个元素，查看这个元素所有的下一级元素，把它们放到队列的末尾。并把这个元素标记为它下一级元素的前驱

找到所要找的元素时结束程序

如果遍历整个树都还没有找到，则结束程序

#include<stdio.h>
#include<stdlib.h>
#define MAX_VALUE 4
int visit[MAX_VALUE];
typedef struct ArcNode
{
    int adjvex;
    struct ArcNode*nextarc;
}ArcNode;
typedef struct VNode
{
    int data;
    ArcNode*firstarc;
}VNode,AdjList[MAX_VALUE];
typedef struct
{
    AdjList vertices;
    int vexnum, arcnum;
}ALGraph;
typedef struct queue
{
    int *pBase;
    int front, rear;
}QUEUE;
int LocateVex(ALGraph G, int v);
void CreatUDG(ALGraph *G);
void PrintUDG(ALGraph G);
void init_queue(QUEUE*Q);
bool isfull_queue(QUEUE*Q);
bool isempty_queue(QUEUE*Q);
void in_queue(QUEUE*Q,int val);
int out_queue(QUEUE*Q);
void BFS(ALGraph G,QUEUE*Q);
void BFST(ALGraph G, QUEUE *Q);
int main()
{
    ALGraph G;
    QUEUE Q;
    CreatUDG(&G);
    PrintUDG(G);
    BFST(G, &Q);
    return 0;
}
int LocateVex(ALGraph G, int v)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (G.vertices[i].data == v)
        {
            return i;
        }
    }
}
void CreatUDG(ALGraph *G)
{
    ArcNode*p, *q;
    int i, j, v1, v2;
    printf("分别输入顶点个数和边的个数：\n");
    scanf("%d%d", &(G->vexnum), &(G->arcnum));
    printf("请输入各个顶点的值：\n");
    for (int i = 0; i < G->vexnum; i++)
    {
        scanf("%d", &(G->vertices[i].data));
        G->vertices[i].firstarc = NULL;
    }
    printf("分别输入各条边的两个顶点：\n");
    for (int k = 0; k < G->arcnum; k++)
    {
        scanf("%d%d", &v1, &v2);
        i = LocateVex(*G, v1);
        j = LocateVex(*G, v2);
        p = (ArcNode*)malloc(sizeof(ArcNode));
        p->adjvex = j;
        p->nextarc = NULL;
        p->nextarc = G->vertices[i].firstarc;
        G->vertices[i].firstarc = p;
        q = (ArcNode*)malloc(sizeof(ArcNode));
        q->adjvex = i;
        q->nextarc = NULL;
        q->nextarc = G->vertices[j].firstarc;
        G->vertices[j].firstarc = q;
    }
}
void PrintUDG(ALGraph G)
{
    ArcNode*p = NULL;
    for (int i = 0; i < G.vexnum; i++)
    {
        printf("第%d条边\n", i + 1);
        p = G.vertices[i].firstarc;
        while (p != NULL)
        {
            printf("%d  ", (p->adjvex) + 1);
            p = p->nextarc;
        }
        printf("\n");
    }
}
void init_queue(QUEUE*Q)
{
    Q->pBase = (int*)malloc((sizeof(int))*4);
    Q->front = 0;
    Q->rear = 0;
}
bool isfull_queue(QUEUE*Q)
{ 
    if (((Q->rear + 1) % MAX_VALUE) == Q->front)
    {
        return true;
    }
    else
        return false;
}
bool isempty_queue(QUEUE*Q)
{
    if (Q->rear == Q->front)
    {
        return true;
    }
    else
        return false;
}
void in_queue(QUEUE*Q, int val)
{
    if (isfull_queue(Q))
    {
        return;
    }
    Q->pBase[Q->rear] = val;
    Q->rear = (Q->rear + 1) % MAX_VALUE;
    //printf("入对元素为%d\n", val);
}
int out_queue(QUEUE*Q)
{
    int temp = 0;
    if (isempty_queue(Q))
        return 0;
    temp = Q->pBase[Q->front];
    Q->front = (Q->front + 1) % MAX_VALUE;
    //printf("\n返回的值为%d\n", temp);
    return temp;
}
void BFS(ALGraph G,QUEUE*Q)
{
    init_queue(Q);
    //自己总结：  注意  下面的这两条语句要放在开头或者在下面的for循环里面在加上条件
    //判断visit数组是否访问过  否则就会当while循环退出的时候 就会继续执行printf("%d  ", G.vertices[i].data)
    //会导致多输出结果
    visit[0] = 1;
    printf("%d  ", G.vertices[0].data);
    for (int i = 0; i < G.vexnum; i++)
    {
        //visit[i] = 1;
        //printf("%d  ", G.vertices[i].data);
        in_queue(Q,i);
        while (!isempty_queue(Q))
        {
            int temp=out_queue(Q);
            ArcNode*p = G.vertices[temp].firstarc;
            while (p!=NULL)
            {
                if (visit[p->adjvex]==0)
                {
                    visit[p->adjvex] = 1;
                    printf("%d  ", G.vertices[p->adjvex].data);
                    in_queue(Q, p->adjvex);
                }
                p = p->nextarc;
            }
        }
    }
}
void BFST(ALGraph G, QUEUE *Q)
{
    for (int i = 0; i < G.vexnum; i++)
    {
        if (!visit[i])
        {
            BFS(G, Q);
        }
    }
}