城市网络：最短路径和最小生成树算法实现

假设有一个城市网络，其中包含n个城市和m条道路。每条道路都连接两个城市，并且具有一个非负的距离值。我们需要找到从给定起始城市到其他所有城市的最短路径和最小生成树。

代码实现

#include <stdio.h>
#include <stdbool.h>
#include <limits.h>
#define MAX_CITIES 100

int numCities, numRoads;
int graph[MAX_CITIES][MAX_CITIES];         

void initializeGraph(int n) {
    numCities = n;
    for (int i = 0; i < numCities; i++) {
        for (int j = 0; j < numCities; j++) {
            graph[i][j] = 0;
        }
    }
}

void addRoad(int city1, int city2, int distance) {
    graph[city1][city2] = distance;
    graph[city2][city1] = distance;
}

int findMinKey(int key[], bool mstSet[]) {
    int min = INT_MAX, min_index;

    for (int i = 0; i < numCities; i++) {
        if (mstSet[i] == false && key[i] < min) {
            min = key[i];
            min_index = i;
        }
    }

    return min_index;
}

void printMST(int parent[]) {
    printf('最小生成树的边：\n');
    for (int i = 1; i < numCities; i++) {
        printf('%d - %d\n', parent[i], i);
    }
}

void printShortestPath(int destination, int parent[]) {
    if (parent[destination] == -1) {
        printf('%d ', destination);
        return;
    }

    printShortestPath(parent[destination], parent);
    printf('-> %d ', destination);
}

void dijkstra(int startCity) {
    int distances[MAX_CITIES];
    bool visited[MAX_CITIES];
    int parent[MAX_CITIES];

    for (int i = 0; i < numCities; i++) {
        distances[i] = INT_MAX;
        visited[i] = false;
        parent[i] = -1;
    }

    distances[startCity] = 0;

    for (int count = 0; count < numCities - 1; count++) {
        int u = findMinKey(distances, visited);
        visited[u] = true;

        for (int v = 0; v < numCities; v++) {
            if (!visited[v] && graph[u][v] && distances[u] != INT_MAX && distances[u] + graph[u][v] < distances[v]) {
                distances[v] = distances[u] + graph[u][v];
                parent[v] = u;
            }
        }
    }

    printf('从起始城市到其他城市的最短路径：\n');
    for (int i = 0; i < numCities; i++) {
        if (i != startCity) {
            printf('从 %d 到 %d 的最短路径为：', startCity, i);
            printShortestPath(i, parent);
            printf('\n');
        }
    }
}

void primMST() {
    int parent[MAX_CITIES];
    int key[MAX_CITIES]; 

    bool mstSet[MAX_CITIES];

    for (int i = 0; i < numCities; i++) {
        key[i] = INT_MAX;
        mstSet[i] = false;
    }

    key[0] = 0;
    parent[0] = -1; 

    for (int count = 0; count < numCities - 1; count++) {
        int u = findMinKey(key, mstSet);
        mstSet[u] = true;

        for (int v = 0; v < numCities; v++) {
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) {
                parent[v] = u;
                key[v] = graph[u][v];
            }
        }
    }

    printMST(parent);
}

int main() {
    int i, city1, city2, distance;

    printf('请输入城市数量：');
    scanf('%d', &numCities);

    printf('请输入道路数量：');
    scanf('%d', &numRoads);

    initializeGraph(numCities);

    printf('请输入每条道路的起始城市、目标城市和距离：\n');
    for (i = 0; i < numRoads; i++) {
        printf('道路 %d：', i + 1);
        scanf('%d %d %d', &city1, &city2, &distance);
        addRoad(city1, city2, distance);
    }

    int startCity;
    printf('请输入起始城市：');
    scanf('%d', &startCity);

    dijkstra(startCity);
    primMST();

    return 0;
}

算法解释

初始化图：通过initializeGraph函数初始化图的邻接矩阵，将所有的边的权重初始化为0。
添加道路：通过addRoad函数添加每条道路的起始城市、目标城市和距离，将对应的权重赋值给图的邻接矩阵。
寻找最小键值：通过findMinKey函数找到最小的键值，该键值对应的城市将被添加到最小生成树的集合中。
打印最小生成树：通过printMST函数打印最小生成树的边。
打印最短路径：通过printShortestPath函数打印从起始城市到其他城市的最短路径。
Dijkstra算法：通过dijkstra函数使用Dijkstra算法找到从起始城市到其他城市的最短路径。
Prim算法：通过primMST函数使用Prim算法找到最小生成树。

代码分析

时间复杂度: O(n^2)，其中n是城市的数量。因为对于每个城市，需要遍历所有的城市来找到最小的键值。
空间复杂度: O(n^2)，因为需要使用一个二维数组来表示图的邻接矩阵。

总结

这段代码实现了一个城市网络的最短路径和最小生成树的算法，使用了Dijkstra算法和Prim算法，并包含详细的代码解释和时间复杂度分析。