用邻接矩阵创建有向网，求最小生成树，最短路径（c语言）。

Question

大神求解！！！用邻接矩阵法创建一个有向网，将有向边直接视为无向边后，得到对应的无向图，则利用Prim算法求取最小生成树MST；利用Dijkstra算法对无向图求取顶点V1对图中其余各点的最短路径。（c语言）

Answer 1

MGraph结构体表示邻接矩阵法表示的有向网，包括顶点数组、邻接矩阵和顶点数、弧数等信息。
MiniSpanTree_Prim函数利用Prim算法求最小生成树，并输出最小生成树的边和权值。
ShortestPath_Dijkstra函数利用Dijkstra算法求单源最短路径，并输出起点到各顶点的最短路径和距离。
在主函数中，先读入顶点和弧的权值，然后调用MiniSpanTree_Prim和ShortestPath_Dijkstra函数求解最小生成树和最短路径。

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define INF INT_MAX // 无穷大

/* 邻接矩阵法表示的有向网 */
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum; // 顶点数和弧数
} MGraph;

/* Prim算法求最小生成树 */
void MiniSpanTree_Prim(MGraph G, int start) {
    int lowcost[MAX_VERTEX_NUM]; // 存储V-U中各顶点到U的最小权值
    int adjvex[MAX_VERTEX_NUM]; // 存储lowcost中最小值对应的顶点编号
    int visited[MAX_VERTEX_NUM] = {0}; // 标记是否已加入U
    int i, j, k, min;
    
    // 初始化lowcost和adjvex数组
    for (i = 0; i < G.vexnum; i++) {
        lowcost[i] = G.arc[start][i];
        adjvex[i] = start;
    }
    visited[start] = 1; // 将起点start加入U
    
    // 依次加入剩余的n-1个顶点
    for (i = 1; i < G.vexnum; i++) {
        // 找到V-U中到U距离最小的顶点k
        min = INF;
        for (j = 0; j < G.vexnum; j++) {
            if (visited[j] == 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        visited[k] = 1; // 将顶点k加入U
        
        // 更新lowcost和adjvex数组
        for (j = 0; j < G.vexnum; j++) {
            if (visited[j] == 0 && G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
    
    // 输出最小生成树的边和权值
    printf("Prim算法求得的最小生成树为：\n");
    for (i = 1; i < G.vexnum; i++) {
        printf("(%d, %d) ", adjvex[i], i);
    }
    printf("\n最小权值为：%d\n", lowcost[1]);
}

/* Dijkstra算法求单源最短路径 */
void ShortestPath_Dijkstra(MGraph G, int start) {
    int dist[MAX_VERTEX_NUM]; // 存储起点start到各顶点的最短距离
    int path[MAX_VERTEX_NUM]; // 存储起点start到各顶点的最短路径中的上一个顶点
    int visited[MAX_VERTEX_NUM] = {0}; // 标记是否已确定最短路径
    int i, j, k, min;
    
    // 初始化dist和path数组
    for (i = 0; i < G.vexnum; i++) {
        dist[i] = G.arc[start][i];
        path[i] = start;
    }
    visited[start] = 1; // 将起点start加入集合S
    
    // 依次确定剩余的n-1个顶点的最短路径
    for (i = 1; i < G.vexnum; i++) {
        // 找到未确定最短路径的顶点中距离start最近的顶点k
        min = INF;
        for (j = 0; j < G.vexnum; j++) {
            if (visited[j] == 0 && dist[j] < min) {
                min = dist[j];
                k = j;
            }
        }
        visited[k] = 1; // 将顶点k加入集合S
        
        // 更新dist和path数组
        for (j = 0; j < G.vexnum; j++) {
            if (visited[j] == 0 && dist[k] + G.arc[k][j] < dist[j]) {
                dist[j] = dist[k] + G.arc[k][j];
                path[j] = k;
            }
        }
    }
    
    // 输出起点start到各顶点的最短路径和距离
    printf("起点为%d的最短路径如下：\n", start);
    for (i = 0; i < G.vexnum; i++) {
        if (i != start) {
            printf("V%d -> V%d: ", start, i);
            j = i;
            while (j != start) {
                printf("V%d <- ", j);
                j = path[j];
            }
            printf("V%d，距离为%d\n", start, dist[i]);
        }
    }
}

int main() {
    MGraph G;
    int i, j;
    int start = 0; // 起点编号
    
    // 输入顶点数和弧数
    printf("请输入有向网的顶点数和弧数：");
    scanf("%d%d", &G.vexnum, &G.arcnum);
    
    // 输入顶点
    printf("请输入%d个顶点：\n", G.vexnum);
    for (i = 0; i < G.vexnum; i++) {
        scanf("%d", &G.vertex[i]);
    }
    
    // 初始化邻接矩阵
    for (i = 0; i < G.vexnum; i++) {
        for (j = 0; j < G.vexnum; j++) {
            G.arc[i][j] = INF;
        }
    }
    
    // 输入弧的权值
    printf("请输入%d条弧的起点、终点和权值：\n", G.arcnum);
    for (i = 0; i < G.arcnum; i++) {
        int start, end, weight;
        scanf("%d%d%d", &start, &end, &weight);
        G.arc[start][end] = weight;
        G.arc[end][start] = weight; // 将有向边直接视为无向边
    }
    
    // 利用Prim算法求最小生成树
    MiniSpanTree_Prim(G, start);
    
    // 利用Dijkstra算法求单源最短路径
    ShortestPath_Dijkstra(G, start);
    
    return 0;
}