10. 图遍历与拓扑排序

习题

#31001

⚡4⏳3

在 30012 的 IntGraph 上实现无权图的最短路查询：

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

bool int_graph_shortest_distance(
    const IntGraph *graph,
    size_t source,
    size_t target,
    size_t *out_distance
);

要求：

1. 仅允许沿边移动；从 source 到 target 不可达时成功返回并将 *out_distance 设为 SIZE_MAX。
2. 参数无效时返回 false，不得修改输出对象；source == target 的距离为 0。
3. 使用 BFS 而不是反复深搜，时间复杂度为 $O(V+E)$，并说明队列中每个顶点最多入队一次的原因。

#31002

⚡5⏳4

在有向 IntGraph 上生成一个拓扑序：

#include <stddef.h>

typedef enum {
    GRAPH_TOPO_OK,
    GRAPH_TOPO_INVALID,
    GRAPH_TOPO_CYCLE
} GraphTopoResult;

GraphTopoResult int_graph_topological_order(
    const IntGraph *graph,
    size_t *out_order,
    size_t capacity,
    size_t *out_count
);

要求：

1. 图必须按有向边解释；存在环时返回 GRAPH_TOPO_CYCLE，输出数组和 *out_count 保持不变。
2. 容量不足、参数无效时返回 GRAPH_TOPO_INVALID，不得修改输出对象。
3. 可使用入度队列或 DFS 三色标记；输出必须包含每个顶点恰好一次，时间复杂度为 $O(V+E)$。

#31003

⚡4⏳4

在 30012 的 IntGraph 上实现深度优先遍历、无向连通分量统计和有向环检测：

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

bool int_graph_dfs_order(
    const IntGraph *graph,
    size_t source,
    size_t *out_order,
    size_t capacity,
    size_t *out_count
);

bool int_graph_count_components(
    const IntGraph *graph,
    size_t *out_components
);

bool int_graph_has_directed_cycle(
    const IntGraph *graph,
    bool *out_cycle
);

要求：

1. int_graph_dfs_order 按邻接表的加边顺序访问，从 source 可达的顶点各输出一次；容量不足或参数无效时返回 false，输出数组和 *out_count 保持不变。说明递归实现或显式栈实现如何保证访问顺序。
2. int_graph_count_components 只接受 30012 创建的无向图；每个顶点必须恰好归入一个连通分量，空图的分量数为 0。参数无效时不得修改输出对象。
3. int_graph_has_directed_cycle 只接受有向图，使用 DFS 的白、灰、黑三色状态（或等价的显式栈状态）检测回到灰色顶点的边；无向图、参数无效或辅助存储分配失败时返回 false，不得修改 *out_cycle。
4. 三个操作都不能改变图及其邻接表；时间复杂度均应为 $O(V+E)$。说明访问标记、栈或递归调用帧的所有权、释放责任以及深度可能达到 $V$ 时的空间需求。