30012：邻接表图与 BFS

题目

实现拥有邻接结点的整数图，并提供按加边顺序输出的 BFS。无向边必须创建两个方向的邻接结点。

解析

每个顶点保存邻接链表的首尾指针，尾指针保证新边可以 $O(1)$ 追加，从而保留加边顺序。无向图加边时先分配两个结点，两个分配都成功后再挂入链表；否则释放已分配结点，图完全不变。

BFS 先把所有访问结果写入临时数组，确认容量足够后再复制到调用方数组。访问标记在入队时设置，所以重复边不会重复入队。

答案

#include <stdbool.h>
#include <stddef.h>
#include <stdlib.h>
#include <string.h>

typedef struct IntGraph IntGraph;
typedef struct GraphEdge GraphEdge;

struct GraphEdge {
    size_t to;
    GraphEdge *next;
};

typedef struct {
    GraphEdge *head;
    GraphEdge *tail;
} Adjacency;

struct IntGraph {
    Adjacency *adj;
    size_t vertex_count;
    bool directed;
};

IntGraph *int_graph_create(size_t vertex_count, bool directed) {
    IntGraph *graph = malloc(sizeof *graph);
    if (graph == NULL) {
        return NULL;
    }
    graph->adj = NULL;
    graph->vertex_count = vertex_count;
    graph->directed = directed;
    if (vertex_count > 0) {
        if (vertex_count > SIZE_MAX / sizeof *graph->adj) {
            free(graph);
            return NULL;
        }
        graph->adj = calloc(vertex_count, sizeof *graph->adj);
        if (graph->adj == NULL) {
            free(graph);
            return NULL;
        }
    }
    return graph;
}

static GraphEdge *make_edge(size_t to) {
    GraphEdge *edge = malloc(sizeof *edge);
    if (edge == NULL) {
        return NULL;
    }
    edge->to = to;
    edge->next = NULL;
    return edge;
}

static void append_edge(Adjacency *adj, GraphEdge *edge) {
    if (adj->tail == NULL) {
        adj->head = edge;
    } else {
        adj->tail->next = edge;
    }
    adj->tail = edge;
}

bool int_graph_add_edge(
    IntGraph *graph,
    size_t from,
    size_t to
) {
    if (graph == NULL || from >= graph->vertex_count ||
        to >= graph->vertex_count) {
        return false;
    }
    GraphEdge *first = make_edge(to);
    if (first == NULL) {
        return false;
    }
    GraphEdge *second = NULL;
    if (!graph->directed) {
        second = make_edge(from);
        if (second == NULL) {
            free(first);
            return false;
        }
    }
    append_edge(&graph->adj[from], first);
    if (second != NULL) {
        append_edge(&graph->adj[to], second);
    }
    return true;
}

void int_graph_destroy(IntGraph *graph) {
    if (graph == NULL) {
        return;
    }
    for (size_t i = 0; i < graph->vertex_count; ++i) {
        GraphEdge *edge = graph->adj[i].head;
        while (edge != NULL) {
            GraphEdge *next = edge->next;
            free(edge);
            edge = next;
        }
    }
    free(graph->adj);
    free(graph);
}

bool int_graph_bfs(
    const IntGraph *graph,
    size_t source,
    size_t *out_order,
    size_t capacity,
    size_t *out_count
) {
    if (graph == NULL || out_count == NULL ||
        source >= graph->vertex_count ||
        graph->vertex_count > SIZE_MAX / sizeof(bool) ||
        graph->vertex_count > SIZE_MAX / sizeof(size_t)) {
        return false;
    }
    bool *visited = calloc(graph->vertex_count, sizeof *visited);
    size_t *queue = malloc(graph->vertex_count * sizeof *queue);
    size_t *order = malloc(graph->vertex_count * sizeof *order);
    if (visited == NULL || queue == NULL || order == NULL) {
        free(visited);
        free(queue);
        free(order);
        return false;
    }

    size_t front = 0;
    size_t back = 0;
    size_t written = 0;
    visited[source] = true;
    queue[back++] = source;
    while (front < back) {
        size_t vertex = queue[front++];
        order[written++] = vertex;
        for (GraphEdge *edge = graph->adj[vertex].head;
             edge != NULL;
             edge = edge->next) {
            if (!visited[edge->to]) {
                visited[edge->to] = true;
                queue[back++] = edge->to;
            }
        }
    }

    if (written > capacity || (written > 0 && out_order == NULL)) {
        free(visited);
        free(queue);
        free(order);
        return false;
    }
    memcpy(out_order, order, written * sizeof *out_order);
    free(visited);
    free(queue);
    free(order);
    *out_count = written;
    return true;
}

建图的每次加边为 $O(1)$；BFS 为 $O(V+E)$，临时数组和队列占用 $O(V)$ 空间。