带分支状态机节点间最短路径的C语言实现方案

状态机结构如下：

G--H
          /
A--B--C--D--E--F

我需要实现一个goToState(target)函数，输入参数为目标状态，函数会从当前状态开始执行所有状态转换，直至到达目标状态。

例如：若当前状态为B，调用goToState(F)，函数会执行状态转换B->C、C->D、D->E、E->F。状态转换支持双向，若当前状态为F，调用goToState(G)，则执行转换F->E、E->D、D->G。

对于线性状态机（无分支如G--H），我会用数组存储合法顺序的转换函数，通过当前状态和目标状态的索引，在循环中调用中间的转换函数即可。但存在分支时该方法失效，请问在C语言中，如何高效编码合法转换并实现该函数？

编辑：正如其他用户指出，我需要的是一种寻找节点间最短路径的算法，只是最初未能准确表述。我需要适用于上述状态图的最简路径查找算法，状态图不会更复杂，无需兼容其他场景。

编辑2：已更新标题以更准确描述问题，感谢各位的评论帮我找到正确术语以便搜索解决方案。

解决方案 #

针对你的简单状态图，用**邻接表+广度优先搜索（BFS）**是最简洁高效的实现方式，既适配分支场景，又不需要复杂的通用算法。

1. 定义状态与转换结构 #

首先给每个状态定义枚举，方便代码中引用：

typedef enum {
    STATE_A, STATE_B, STATE_C, STATE_D, STATE_E, STATE_F, STATE_G, STATE_H,
    STATE_COUNT // 用于标记数组末尾，计算状态总数
} State;

然后定义状态转换函数的类型，以及邻接表结构（存储每个状态的可达邻居和对应的转换函数）：

// 状态转换函数：实现从from到to的具体逻辑
typedef void (*StateTransition)(State from, State to);

// 邻接表节点：记录邻居状态和对应的转换函数
typedef struct {
    State neighbor;
    StateTransition transition;
} AdjacentNode;

// 全局邻接表：每个状态的可达邻居列表，末尾用STATE_COUNT标记结束
AdjacentNode adjacency[STATE_COUNT][4] = {
    // STATE_A
    {{STATE_B, transition_A_to_B}, {STATE_COUNT, NULL}},
    // STATE_B
    {{STATE_A, transition_B_to_A}, {STATE_C, transition_B_to_C}, {STATE_COUNT, NULL}},
    // STATE_C
    {{STATE_B, transition_C_to_B}, {STATE_D, transition_C_to_D}, {STATE_COUNT, NULL}},
    // STATE_D
    {{STATE_C, transition_D_to_C}, {STATE_E, transition_D_to_E}, {STATE_G, transition_D_to_G}, {STATE_COUNT, NULL}},
    // STATE_E
    {{STATE_D, transition_E_to_D}, {STATE_F, transition_E_to_F}, {STATE_COUNT, NULL}},
    // STATE_F
    {{STATE_E, transition_F_to_E}, {STATE_COUNT, NULL}},
    // STATE_G
    {{STATE_D, transition_G_to_D}, {STATE_H, transition_G_to_H}, {STATE_COUNT, NULL}},
    // STATE_H
    {{STATE_G, transition_H_to_G}, {STATE_COUNT, NULL}}
};

你需要为每个转换实现具体的函数，比如：

void transition_A_to_B(State from, State to) {
    // 这里写A到B的状态转换逻辑，比如更新硬件、修改全局变量等
}

void transition_B_to_A(State from, State to) {
    // B到A的转换逻辑
}

// 其余转换函数类似实现

2. 实现BFS最短路径查找 #

BFS天生适合找无权重图的最短路径，你的状态图所有转换权重相同，刚好适用。我们需要记录每个节点的前驱状态和对应的转换函数，找到路径后回溯得到完整转换序列：

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

#define MAX_PATH_LENGTH STATE_COUNT

// 存储路径信息：包含每一步的目标状态和对应的转换函数
typedef struct {
    State steps[MAX_PATH_LENGTH];
    StateTransition transitions[MAX_PATH_LENGTH];
    int length;
} StatePath;

// 查找从current到target的最短路径，成功返回true，路径存入path
bool findShortestPath(State current, State target, StatePath *path) {
    if (current == target) {
        path->length = 0;
        return true;
    }

    // 初始化辅助数组：标记已访问状态、记录前驱状态和转换函数
    bool visited[STATE_COUNT] = {false};
    State predecessor[STATE_COUNT];
    StateTransition predTrans[STATE_COUNT];
    memset(predecessor, STATE_COUNT, sizeof(predecessor)); // 用STATE_COUNT表示无前置
    memset(predTrans, 0, sizeof(predTrans));

    // BFS队列：存储待遍历的状态
    State queue[MAX_PATH_LENGTH];
    int front = 0, rear = 0;
    queue[rear++] = current;
    visited[current] = true;

    // 开始BFS遍历
    while (front < rear) {
        State currNode = queue[front++];

        // 遍历当前节点的所有邻居
        for (int i = 0; adjacency[currNode][i].neighbor != STATE_COUNT; i++) {
            State neighbor = adjacency[currNode][i].neighbor;
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                predecessor[neighbor] = currNode;
                predTrans[neighbor] = adjacency[currNode][i].transition;
                queue[rear++] = neighbor;

                // 找到目标状态，提前终止遍历
                if (neighbor == target) {
                    front = rear;
                    break;
                }
            }
        }
    }

    // 目标状态不可达（你的状态图不会出现此情况）
    if (predecessor[target] == STATE_COUNT) {
        return false;
    }

    // 回溯路径：从target倒推回current，再反转得到正序路径
    State tempSteps[MAX_PATH_LENGTH];
    StateTransition tempTrans[MAX_PATH_LENGTH];
    int tempLen = 0;
    State node = target;

    while (node != current) {
        tempSteps[tempLen] = node;
        tempTrans[tempLen] = predTrans[node];
        tempLen++;
        node = predecessor[node];
    }

    // 反转得到从current到target的正序路径
    path->length = tempLen;
    for (int i = 0; i < tempLen; i++) {
        path->steps[i] = tempSteps[tempLen - 1 - i];
        path->transitions[i] = tempTrans[tempLen - 1 - i];
    }

    return true;
}

3. 实现goToState函数 #

基于路径查找函数，goToState只需要遍历路径执行转换即可：

// 当前状态（可以改成全局变量或函数参数，根据你的需求调整）
State currentState = STATE_A;

void goToState(State target) {
    StatePath path;
    if (!findShortestPath(currentState, target, &path)) {
        // 处理不可达情况，比如打印错误日志
        return;
    }

    // 依次执行每一步状态转换
    for (int i = 0; i < path.length; i++) {
        State nextState = path.steps[i];
        // 调用转换函数
        path.transitions[i](currentState, nextState);
        // 更新当前状态
        currentState = nextState;
    }
}

4. 针对当前状态图的简化优化 #

如果你的状态图永远不会修改，也可以跳过BFS，直接手动定义每个状态到其他状态的转换序列，但这种方式维护性差，一旦状态图变更就需要大量修改代码。BFS方案虽然多了几行代码，但扩展性和维护性更好，适合你的场景。

内容的提问来源于stack exchange，提问作者stefanos