面试题：C语言实现简单图的广度优先搜索

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

// 邻接表节点结构体定义
struct AdjListNode {
    int dest;
    struct AdjListNode* next;
};

// 邻接表结构体定义
struct AdjList {
    struct AdjListNode *head;
};

// 图结构体定义
struct Graph {
    int V;
    struct AdjList* array;
};

// 创建一个新的邻接表节点
struct AdjListNode* newAdjListNode(int dest) {
    struct AdjListNode* newNode = (struct AdjListNode*)malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建一个图
struct Graph* createGraph(int V) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;

    // 为邻接表数组分配内存
    graph->array = (struct AdjList*)malloc(V * sizeof(struct AdjList));

    // 初始化每个邻接表为 NULL
    for (int i = 0; i < V; ++i) {
        graph->array[i].head = NULL;
    }

    return graph;
}

// 向图中添加边
void addEdge(struct Graph* graph, int src, int dest) {
    // 添加从 src 到 dest 的边
    struct AdjListNode* newNode = newAdjListNode(dest);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;

    // 因为是无向图，所以也要添加从 dest 到 src 的边
    newNode = newAdjListNode(src);
    newNode->next = graph->array[dest].head;
    graph->array[dest].head = newNode;
}

// 队列结构体定义
struct Queue {
    int front, rear;
    int capacity;
    int* array;
};

// 创建一个队列
struct Queue* createQueue(int capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->rear = 0;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

// 检查队列是否已满
int isQueueFull(struct Queue* queue) {
    return (queue->rear + 1) % queue->capacity == queue->front;
}

// 检查队列是否为空
int isQueueEmpty(struct Queue* queue) {
    return queue->front == queue->rear;
}

// 入队操作
void enqueue(struct Queue* queue, int item) {
    if (isQueueFull(queue)) {
        return;
    }
    queue->array[queue->rear] = item;
    queue->rear = (queue->rear + 1) % queue->capacity;
}

// 出队操作
int dequeue(struct Queue* queue) {
    if (isQueueEmpty(queue)) {
        return -1;
    }
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    return item;
}

// 广度优先搜索
void BFS(struct Graph* graph, int start) {
    // 标记数组，用于记录顶点是否被访问过
    int* visited = (int*)malloc(graph->V * sizeof(int));
    for (int i = 0; i < graph->V; ++i) {
        visited[i] = 0;
    }

    // 创建队列并将起始顶点入队
    struct Queue* queue = createQueue(graph->V);
    visited[start] = 1;
    enqueue(queue, start);

    while (!isQueueEmpty(queue)) {
        // 取出队首顶点并打印
        int currentVertex = dequeue(queue);
        printf("%d ", currentVertex);

        // 遍历当前顶点的邻接表
        struct AdjListNode* adjListNode = graph->array[currentVertex].head;
        while (adjListNode != NULL) {
            int adjacentVertex = adjListNode->dest;
            if (!visited[adjacentVertex]) {
                visited[adjacentVertex] = 1;
                enqueue(queue, adjacentVertex);
            }
            adjListNode = adjListNode->next;
        }
    }

    // 释放标记数组和队列的内存
    free(visited);
    free(queue->array);
    free(queue);
}
星途面试题库

面试题：C语言实现简单图的广度优先搜索

知识考点

面试题答案
