构建图的最小生成树或求最短路径C语言

最小生成树算法：

使用Prim算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void prim(int start_vertex) {
    bool visited[MAX_VERTICES] = {false}; // 顶点是否已被访问
    int distance[MAX_VERTICES]; // 到各顶点的距离
    int parent[MAX_VERTICES]; // 生成树的父节点

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
        distance[i] = INF;
        parent[i] = -1;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices - 1; i++) { // 循环n-1次，构建n-1条边
        int min_distance = INF;
        int u; // 最小距离对应的顶点编号
        // 找到未被访问过的、到起点距离最短的顶点
        for (int j = 0; j < num_vertices; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        visited[u] = true; // 对该顶点进行标记
        // 更新与该顶点相邻的顶点到起点的距离
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && !visited[v] && adj_matrix[u][v] < distance[v]) {
                distance[v] = adj_matrix[u][v];
                parent[v] = u;
            }
        }
    }

    // 输出生成树
    printf("生成树：\n");
    for (int i = 1; i < num_vertices; i++) { // 从第二个顶点开始，依次输出每个顶点的父节点和边的权值
        printf("%d - %d (%d)\n", parent[i], i, adj_matrix[i][parent[i]]);
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    prim(start_vertex);
    return 0;
}

使用Kruskal算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

int parent[MAX_VERTICES]; // 并查集数组

// 并查集查找根节点
int find(int x) {
    while (parent[x] != -1) {
        x = parent[x];
    }
    return x;
}

void kruskal() {
    int total_weight = 0; // 最小生成树的总权值
    int edge_count = 0; // 已选取的边的数量

    // 初始化并查集
    for (int i = 0; i < num_vertices; i++) {
        parent[i] = -1;
    }

    // 对所有边按权值从小到大排序
    struct {
        int u, v, weight;
    } edges[num_vertices * num_vertices]; // 边的数组，最多有n^2条边
    int count = 0; // 实际边的数量
    for (int i = 0; i < num_vertices; i++) {
        for (int j = i + 1; j < num_vertices; j++) { // 使用邻接矩阵，只需要遍历矩阵的上三角
            if (adj_matrix[i][j] != 0) {
                edges[count].u = i;
                edges[count].v = j;
                edges[count].weight = adj_matrix[i][j];
                count++;
            }
        }
    }
    for (int i = 0; i < count - 1; i++) { // 冒泡排序
        for (int j = 0; j < count - i - 1; j++) {
            if (edges[j].weight > edges[j+1].weight) {
                struct {
                    int u, v, weight;
                } temp = edges[j];
                edges[j] = edges[j+1];
                edges[j+1] = temp;
            }
        }
    }

    // 依次选取权值最小的边，如果两个顶点不在同一个连通分量中，则加入最小生成树
    printf("生成树：\n");
    while (edge_count < num_vertices - 1) { // 已选取的边的数量小于n-1时，继续选取
        int u = edges[edge_count].u;
        int v = edges[edge_count].v;
        int weight = edges[edge_count].weight;
        int root_u = find(u);
        int root_v = find(v);
        if (root_u != root_v) { // 如果两个顶点不在同一个连通分量中
            parent[root_u] = root_v; // 合并连通分量
            printf("%d - %d (%d)\n", u, v, weight); // 输出边
            total_weight += weight; // 加上边的权值
        }
        edge_count++;
    }
    printf("最小权值和：%d\n", total_weight);
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    kruskal();
    return 0;
}

最短路径算法：

使用Dijkstra算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void dijkstra(int start_vertex) {
    bool visited[MAX_VERTICES] = {false}; // 顶点是否已被访问
    int distance[MAX_VERTICES]; // 起点到各顶点的距离

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        visited[i] = false;
        distance[i] = INF;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices; i++) { // 循环n次，每次确定一个顶点的最短路径
        int min_distance = INF;
        int u; // 最小距离对应的顶点编号
        // 找到未被访问过的、到起点距离最短的顶点
        for (int j = 0; j < num_vertices; j++) {
            if (!visited[j] && distance[j] < min_distance) {
                min_distance = distance[j];
                u = j;
            }
        }
        visited[u] = true; // 对该顶点进行标记
        // 更新与该顶点相邻的顶点到起点的距离
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && !visited[v] && distance[u] + adj_matrix[u][v] < distance[v]) {
                distance[v] = distance[u] + adj_matrix[u][v];
            }
        }
    }

    // 输出到各顶点的最短路径
    printf("起点到各顶点的最短路径：\n");
    for (int i = 0; i < num_vertices; i++) {
        printf("%d -> %d: %d\n", start_vertex, i, distance[i]);
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    dijkstra(start_vertex);
    return 0;
}

使用Bellman-Ford算法实现：

#include <stdio.h>
#include <stdbool.h> // bool类型需要用到

#define MAX_VERTICES 100
#define INF 1000000

int num_vertices; // 图中顶点个数
int adj_matrix[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵

void bellman_ford(int start_vertex) {
    int distance[MAX_VERTICES]; // 起点到各顶点的距离

    // 初始化
    for (int i = 0; i < num_vertices; i++) {
        distance[i] = INF;
    }
    distance[start_vertex] = 0;

    for (int i = 0; i < num_vertices - 1; i++) { // 循环n-1次，每次松弛n-1条边
        for (int u = 0; u < num_vertices; u++) {
            for (int v = 0; v < num_vertices; v++) {
                if (adj_matrix[u][v] != 0 && distance[u] + adj_matrix[u][v] < distance[v]) {
                    distance[v] = distance[u] + adj_matrix[u][v];
                }
            }
        }
    }

    // 判断是否存在负权回路
    bool has_negative_cycle = false;
    for (int u = 0; u < num_vertices; u++) {
        for (int v = 0; v < num_vertices; v++) {
            if (adj_matrix[u][v] != 0 && distance[u] + adj_matrix[u][v] < distance[v]) {
                has_negative_cycle = true;
                break;
            }
        }
    }

    if (has_negative_cycle) {
        printf("图中存在负权回路\n");
    } else {
        // 输出到各顶点的最短路径
        printf("起点到各顶点的最短路径：\n");
        for (int i = 0; i < num_vertices; i++) {
            printf("%d -> %d: %d\n", start_vertex, i, distance[i]);
        }
    }
}

int main() {
    printf("请输入图中顶点个数：");
    scanf("%d", &num_vertices);
    printf("请输入图的邻接矩阵：\n");
    for (int i = 0; i < num_vertices; i++) {
        for (int j = 0; j < num_vertices; j++) {
            scanf("%d", &adj_matrix[i][j]);
        }
    }
    printf("请输入起点编号：");
    int start_vertex;
    scanf("%d", &start_vertex);
    bellman_ford(start_vertex);
    return 0;
}