数据结构图论用C语言实现骑马修栅栏

以下是使用C语言实现数据结构图论的骑马修栅栏算法的代码：

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

// 图的邻接表结构体
struct AdjListNode {
    int dest;    // 目标节点编号
    int weight;  // 边的权重
    struct AdjListNode* next;
};

// 图的邻接表头结构体
struct AdjList {
    struct AdjListNode* head;
};

// 图结构体
struct Graph {
    int V;            // 节点数
    struct AdjList* array;
};

// 栅栏结构体
struct Fence {
    int id;        // 栅栏编号
    int height;    // 栅栏高度
};

// 栅栏比较函数
int cmp(const void *a, const void *b) {
    const struct Fence *fa = a;
    const struct Fence *fb = b;
    return fa->height - fb->height;
}

// 创建邻接表节点
struct AdjListNode* newAdjListNode(int dest, int weight) {
    struct AdjListNode* newNode = (struct AdjListNode*) malloc(sizeof(struct AdjListNode));
    newNode->dest = dest;
    newNode->weight = weight;
    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));
    for (int i = 0; i < V; ++i)
        graph->array[i].head = NULL;
    return graph;
}

// 添加边
void addEdge(struct Graph* graph, int src, int dest, int weight) {
    struct AdjListNode* newNode = newAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
}

// 迪杰斯特拉算法
void dijkstra(struct Graph* graph, int start, int* dist) {
    int V = graph->V;
    int* visited = (int*) malloc(V * sizeof(int));
    for (int i = 0; i < V; i++) {
        visited[i] = 0;
        dist[i] = INT_MAX;
    }
    dist[start] = 0;

    for (int count = 0; count < V - 1; count++) {
        int u = -1;
        for (int i = 0; i < V; i++)
            if (!visited[i] && (u == -1 || dist[i] < dist[u]))
                u = i;

        visited[u] = 1;

        struct AdjListNode* node = graph->array[u].head;
        while (node != NULL) {
            int v = node->dest;
            int weight = node->weight;
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v])
                dist[v] = dist[u] + weight;
            node = node->next;
        }
    }

    free(visited);
}

// 骑马修栅栏函数
void horseRepairFence(struct Fence *fences, int n, struct Graph* graph, int maxDiff) {
    int* dist = (int*) malloc(n * sizeof(int));
    dijkstra(graph, 0, dist);
    int lastHeight = fences[0].height;    // 上一个栅栏的高度
    printf("修建栅栏：%d\n", fences[0].id);
    for (int i = 1; i < n; i++) {
        if (dist[i] == INT_MAX) {
            printf("无法修建到 %d 号栅栏\n", fences[i].id);
            continue;
        }
        if (dist[i] - (fences[i].height - lastHeight) > maxDiff) {    // 如果与上一个栅栏的高度差超过了最大值
            printf("修建栅栏：%d\n", fences[i].id);
            lastHeight = fences[i].height;
        }
    }
    free(dist);
}

int main() {
    int n;    // 栅栏数量
    int maxDiff;    // 最大高度差
    printf("请输入栅栏数量和最大高度差：");
    scanf("%d %d", &n, &maxDiff);

    // 读入栅栏信息
    struct Fence *fences = malloc(n * sizeof(struct Fence));
    for (int i = 0; i < n; i++) {
        fences[i].id = i + 1;
        scanf("%d", &fences[i].height);
    }

    // 根据栅栏高度排序
    qsort(fences, n, sizeof(struct Fence), cmp);

    // 创建图
    struct Graph* graph = createGraph(n);
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            int weight = fences[j].id - fences[i].id;    // 权重为栅栏之间的距离
            addEdge(graph, i, j, weight);
            addEdge(graph, j, i, weight);
        }
    }

    // 骑马修栅栏
    horseRepairFence(fences, n, graph, maxDiff);

    free(fences);
    free(graph);
    return 0;
}

代码中使用了图的邻接表结构体来存储图的信息，通过`createGraph`函数创建了一个V个节点的图，并使用`addEdge`函数添加了所有的边。在`horseRepairFence`函数中，首先使用迪杰斯特拉算法求出所有节点到起点的最短路径，然后根据栅栏高度和与上一个栅栏的距离以及最短路径来判断是否修建栅栏。最后在`main`函数中读入栅栏信息并进行排序，创建图，然后调用`horseRepairFence`函数进行修建栅栏。