关于图的数据结构和算法实现，可做参考。

---

数据结构定义和相关函数

数据结构

/* 优先队列节点 */
typedef struct
{
    int first;
    int second;
} node_t;

typedef bool (*cmp)(const void *, const void *);

/* 优先队列，用于实现最短路径算法 */
typedef struct
{
    node_t *arr;
    int capacity;
    int queueSize;
    cmp compare;
} priority_queue_t;

/* 边 */
typedef struct edge_s
{
    int to;
    int cost;
    struct edge_s *next;
} edge_t;

/* 图 */
typedef struct
{
    edge_t **graph;
    int nodeSize;
} graph_t;

优先队列相关函数

/* 创建优先队列 */
priority_queue_t *create_priority_queue(int size, cmp compare)
{
    priority_queue_t *obj = (priority_queue_t *)malloc(sizeof(priority_queue_t));
    obj->arr = (node_t *)malloc(sizeof(node_t) * size);
    obj->queueSize = 0;
    obj->capacity = size;
    obj->compare = compare;
    return obj;
}

/* 释放优先队列 */
void free_priority_queue(priority_queue_t *obj)
{
    free(obj->arr);
    free(obj);
}

/* 创建节点 */
node_t *create_node(long long x, int y)
{
    node_t *obj = (node_t *)malloc(sizeof(node_t));
    obj->first = x;
    obj->second = y;
    return obj;
}

/* 入队 */
void push(priority_queue_t *obj, node_t *node)
{
    memcpy_s(&obj->arr[obj->queueSize], sizeof(node_t), node, sizeof(node_t));
    for (int i = obj->queueSize; i > 0 && obj->compare(&obj->arr[(i - 1) / 2], &obj->arr[i]); i = (i - 1) / 2) {
        swap(obj->arr, i, (i - 1) / 2);
    }
    obj->queueSize++;
}

/* 出队 */
node_t* pop(priority_queue_t *obj)
{
    swap(obj->arr, 0, obj->queueSize - 1);
    down(obj->arr, obj->queueSize - 1, 0, obj->compare);
    node_t *ret =  &obj->arr[obj->queueSize - 1];
    obj->queueSize--;
    return ret;
}

/* 队列是否为空 */
bool is_empty(priority_queue_t *obj)
{
    return obj->queueSize == 0;
}

/* 队头节点 */
node_t* top(priority_queue_t *obj)
{
    if (obj->queueSize == 0) {
        return NULL;
    } else {
        return &obj->arr[0];
    }
}

/* 交换两个节点 */
static void swap(node_t *arr, int i, int j)
{
    node_t tmp;
    memcpy_s(&tmp, sizeof(node_t), &arr[i], sizeof(node_t));
    memcpy_s(&arr[i], sizeof(node_t), &arr[j], sizeof(node_t));
    memcpy_s(&arr[j], sizeof(node_t), &tmp, sizeof(node_t));
}

/* 堆的交换 */
static void down(node_t *arr, int size, int i, cmp compare)
{
    for (int k = 2 * i + 1; k < size; k = 2 * k + 1) {
        // 父节点 (k - 1) / 2，左子节点 k，右子节点 k + 1
        if (k + 1 < size && compare(&arr[k], &arr[k + 1])) {
            k++;
        }
        if (compare(&arr[k], &arr[(k - 1) / 2])) {
            break;
        }
        swap(arr, k, (k - 1) / 2);
    }
}

/* heapify 函数用于将传入的 priority_queue_t 优先队列对象的内部数组调整为堆结构。它通过从最后一个非叶子节点开始，依次向下调整每个节点，以确保整个队列满足堆的性质。 */
void heapify(priority_queue_t *obj)
{
    for (int i = obj->queueSize / 2 - 1; i >= 0; i--) {
        down(obj->arr, obj->queueSize, i, obj->compare);
    }
}

/* 两个节点的比较函数 */
bool greater(const void *a, const void *b)
{
   return ((node_t *)a)->first > ((node_t *)b)->first;
}

边相关函数

/* 创建边 */
edge_t *create_edge(int to, int cost)
{
    edge_t *obj = (edge_t *)malloc(sizeof(edge_t));
    obj->to = to;
    obj->cost = cost;
    obj->next = NULL;
    return obj;
}

/* 释放边列表 */
void free_edge_list(edge_t *list)
{
    while (list) {
        edge_t *p = list;
        list = list->next;
        free(p);
    }
}

图相关函数

/* 创建图 */
graph_t* graph_create(int n, int** edges, int edgesSize, int* edgesColSize)
{
    graph_t *obj = (graph_t *)malloc(sizeof(graph_t));
    obj->nodeSize = n;
    obj->graph = (edge_t **)malloc(sizeof(edge_t *) * n);
    for (int i = 0; i < n; i++) {
        obj->graph[i] = NULL;
    }
    for (int i = 0; i < edgesSize; i++) {
        int x = edges[i][0];
        int y = edges[i][1];
        int cost = edges[i][2];
        edge_t *e = (edge_t *)malloc(sizeof(edge_t));
        e->to = y;
        e->cost = cost;
        e->next = obj->graph[x];
        obj->graph[x] = e;
    }

    return obj;
}

/* 释放图 */
void graph_free(graph_t* obj)
{
    for (int i = 0; i < obj->nodeSize; i++) {
        free_edge_list(obj->graph[i]);
    }
    free(obj->graph);
    free(obj);
}

/* 给图添加边 */
void graph_add_edge(graph_t* obj, int* edge, int edgeSize)
{
    int x = edge[0];
    int y = edge[1];
    int cost = edge[2];
    edge_t *e = create_edge(y, cost);
    e->next = obj->graph[x];
    obj->graph[x] = e;
}

相关算法

dijkstra最短路径算法

/**
 * 最短路径算法dijkstra
 * 详细解释：
 * 该算法用于计算图中两个节点之间的最短路径。
 * 它使用优先队列来高效地选择当前距离最短的节点进行扩展。
 * 算法初始化时，将所有节点的距离设置为无穷大，起始节点的距离设置为0。
 * 然后将起始节点加入优先队列。
 * 在每次迭代中，从优先队列中取出距离最短的节点，检查其所有邻居节点。
 * 如果通过当前节点到达邻居节点的距离小于已知的距离，则更新邻居节点的距离并将其加入优先队列。
 * 该过程持续直到找到目标节点或优先队列为空（表示无法到达目标节点）。
 * 最终返回起始节点到目标节点的最短距离，如果无法到达则返回-1。
 */
int graph_shortest_path(graph_t* obj, int node1, int node2)
{
    int n = obj->nodeSize;
    int dist[n];
    priority_queue_t *pq = create_priority_queue(n * n, greater);

    for (int i = 0; i < n; i++) {
        dist[i] = INT_MAX;
    }

    dist[node1] = 0;
    node_t val;
    val.first = 0;
    val.second = node1;
    push(pq, &val);
    while (!is_empty(pq)) {
        node_t *p = pop(pq);
        int cost = p->first;
        int cur = p->second;

        if (cur == node2) {
            free_priority_queue(pq);
            return cost;
        }

        for (edge_t *pEntry = obj->graph[cur]; pEntry; pEntry = pEntry->next) {
            int next = pEntry->to;
            int ncost = pEntry->cost;
            if (dist[next] > cost + ncost) {
                dist[next] = cost + ncost;
                val.first = cost + ncost;
                val.second = next;
                push(pq, &val);
            }
        }
    }
    free_priority_queue(pq);
    return -1;
}

« KMP算法笔记