数据结构prim、kruskal、Floyd、Dijkstra算法C语言代码

好的，下面是这些算法的C语言代码示例：

1. Prim算法（最小生成树）：

#include <stdio.h>
#define INF 9999999

int graph[100][100], spanningTree[100], minWeight;

void prim(int n) {
    int visited[100] = {0}, i, j, min, u, v;

    visited[0] = 1;
    for (i = 1; i < n; i++) {
        min = INF;
        for (j = 0; j < n; j++) {
            if (visited[j]) {
                for (int k = 0; k < n; k++) {
                    if (!visited[k] && graph[j][k] && graph[j][k] < min) {
                        min = graph[j][k];
                        u = j;
                        v = k;
                    }
                }
            }
        }
        
        visited[v] = 1;
        spanningTree[u] = v;
        minWeight += min;
    }
}

int main() {
    int n, i, j;
    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    
    printf("Enter the adjacency matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    
    prim(n);
    
    printf("Minimum spanning tree:\n");
    for (i = 0; i < n - 1; i++) {
        printf("%d - %d\n", spanningTree[i], i);
    }
    
    printf("Minimum weight: %d\n", minWeight);
    
    return 0;
}

2. Kruskal算法（最小生成树）：

#include <stdio.h>

#define MAX 30

typedef struct edge {
    int u;
    int v;
    int weight;
} edge;

typedef struct edgelist {
    edge data[MAX];
    int n;
} edgelist;

edgelist elist;

int parent[MAX];

int find(int i) {
    while (parent[i])
        i = parent[i];
    return i;
}

void union_ij(int i, int j) {
    if (i != j) {
        parent[j] = i;
    }
}

void kruskal(int n) {
    int i, j, a, b, u, v;
    int ne = 0, mincost = 0;
    
    for (i = 0; i < n; i++) {
        parent[i] = 0;
    }
    
    for (i = 0; i < elist.n; i++) {
        u = elist.data[i].u;
        v = elist.data[i].v;
        a = find(u);
        b = find(v);
        
        if (a != b) {
            printf("(%d, %d) -> %d\n", u, v, elist.data[i].weight);
            mincost += elist.data[i].weight;
            ne++;
            union_ij(a, b);
        }
        
        if (ne == n - 1)
            break;
    }
    
    printf("Minimum cost: %d\n", mincost);
}

int main() {
    int n, i, j, cost;
    
    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    
    printf("Enter the adjacency matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &cost);
            if (cost != 0) {
                elist.data[elist.n].u = i;
                elist.data[elist.n].v = j;
                elist.data[elist.n].weight = cost;
                elist.n++;
            }
        }
    }
    
    kruskal(n);
    
    return 0;
}

3. Floyd算法（全源最短路径）：

#include <stdio.h>

#define INF 9999
#define MAX 100

int graph[MAX][MAX];

void floydWarshall(int n) {
    int dist[n][n], i, j, k;
    
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            dist[i][j] = graph[i][j];
        }
    }
    
    for (k = 0; k < n; k++) {
        for (i = 0; i < n; i++) {
            for (j = 0; j < n; j++) {
                if (dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    printf("Shortest distances between every pair of vertices:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (dist[i][j] == INF) {
                printf("INF ");
            } else {
                printf("%d ", dist[i][j]);
            }
        }
        printf("\n");
    }
}

int main() {
    int n, i, j;
    
    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    
    printf("Enter the adjacency matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    
    floydWarshall(n);
    
    return 0;
}

4. Dijkstra算法（单源最短路径）：

#include <stdio.h>
#define INF 999999

int graph[100][100], dist[100], visited[100];

int minDistance(int n) {
    int min = INF, minIndex, i;
    
    for (i = 0; i < n; i++) {
        if (!visited[i] && dist[i] <= min) {
            min = dist[i];
            minIndex = i;
        }
    }
    
    return minIndex;
}

void dijkstra(int n, int start) {
    int i, j, u;
    
    for (i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    
    dist[start] = 0;
    
    for (i = 0; i < n - 1; i++) {
        u = minDistance(n);
        visited[u] = 1;
        
        for (j = 0; j < n; j++) {
            if (!visited[j] && graph[u][j] && dist[u] != INF && dist[u] + graph[u][j] < dist[j]) {
                dist[j] = dist[u] + graph[u][j];
            }
        }
    }
    
    printf("Shortest distances from node %d:\n", start);
    for (i = 0; i < n; i++) {
        printf("%d to %d: %d\n", start, i, dist[i]);
    }
}

int main() {
    int n, i, j, start;
    
    printf("Enter the number of nodes: ");
    scanf("%d", &n);
    
    printf("Enter the adjacency matrix:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    
    printf("Enter the starting node: ");
    scanf("%d", &start);
    
    dijkstra(n, start);
    
    return 0;
}

以上是这些算法的简单C语言代码示例，供参考。请根据实际情况进行适当修改和调整。