c语言实现广度优先算法

1.源码实现

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <malloc.h>

int map[5][5] = {{0, 1, 0, 0, 0}, {0, 1, 0, 1, 0}, {0, 0, 0, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 0, 1, 0}};
char flag[5][5] = {{0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}, {0, 0, 0, 0, 0}};
int R[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

struct State {
    int x, y;
    int t;
    struct State *parent;
};

struct Queue {
    struct State *status;
    struct Queue *next;
    struct Queue *last;
};

void QueuePush(struct Queue **queue, struct State *status)
{
    struct Queue *last = (struct Queue *)malloc(sizeof(struct Queue));

    last->status = status;

    if((*queue) == NULL)
    {
        *queue = last;

        (*queue)->next = NULL;
        (*queue)->last = last;

        return;
    }

    if((*queue)->next == NULL)
    {
        (*queue)->next = last;
    }

    (*queue)->last->next = last;
    (*queue)->last = last;
}

void QueuePop(struct Queue **queue)
{
    struct Queue *top = (*queue);

    if(queue == NULL || *queue == NULL)
    {
        return;
    }

    if((*queue)->next == NULL)
    {
        free(*queue);

        *queue = NULL;

        return;
    }

    (*queue) = (*queue)->next;

    (*queue)->last = top->last;

    free(top);
}

struct State *QueueFront(const struct Queue *queue)
{
    if(queue == NULL)
    {
        return NULL;
    }

    return queue->status;
}

char QueueIsEmpty(const struct Queue *queue)
{
    if(queue == NULL)
    {
        return 1;
    }

    return 0;
}

void QueueFree(struct Queue **queue)
{
    while(!QueueIsEmpty(*queue))
    {
        QueuePop(queue);
    }
}

struct State *BFS()
{
    struct Queue *Q = NULL;
    int x = 0;
    int y = 0;
    int t = 0;
    int i;
    struct State *start = (struct State *)malloc(sizeof(struct State));

    start->x = start->y = 0;
    start->t = 0;
    start->parent = NULL;

    QueuePush(&Q, start);

    while(QueueIsEmpty(Q) == 0)
    {
        struct State *temp = QueueFront(Q);

        QueuePop(&Q);

        for(i=0; i<4; i++)
        {
            x = temp->x + R[i][0];
            y = temp->y + R[i][1];

            if(x < 0 || y < 0 || x > 4 || y > 4)
            {
                continue;
            }

            if(flag[x][y] == 1)
            {
                continue;
            }

            if(map[x][y] == 1)
            {
                continue;
            }

            struct State *tempS = (struct State *)malloc(sizeof(struct State));

            tempS->x = x;
            tempS->y = y;
            tempS->t = temp->t + 1;
            tempS->parent = temp;

            if(x == 4 && y == 4)
            {
                QueueFree(&Q);

                return tempS;
            }

            QueuePush(&Q, tempS);

            flag[x][y] = 1;
        }
    }

    QueueFree(&Q);

    return start;
}

int main()
{
    struct State *q = BFS();
    struct State *p = q;
    struct State *prev = NULL;
    struct State *next = q->parent;

    while(q != NULL)
    {
        next = q->parent;

        q->parent = prev;

        prev = q;
        q = next;
    }

    q = prev;
    p = q;

    while(q != NULL)
    {
        printf("(%d, %d)\n", q->x, q->y);

        p = q;

        free(q);

        q = p->parent;
    }

    return 0;
}

2.编译源码

$ gcc -o test test.c -std=c89

3.运行及其结果

$ ./test
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)