求下面问题的完整答案，图在链接里

已知顶点集合{a,b,c,d,e,f}，构成的无向图的带权邻接矩阵如下：https://cg.sau.edu.cn/userfiles/image/1483599133822034852.png
① 画出无向带权图；   
② 给出无向带权图的最小生成树；

#include<bits/stdc++.h>
#define NUM 6
using namespace std;

//利用二维数组创建有向图的邻接矩阵
void CreateMatrix(int mat[NUM][NUM]);
//利用Prim算法求解最小生成树
void DijkstraSearch(int mat[NUM][NUM], int i, int visit[NUM], int dist[NUM], int path[NUM]);

int main()
{
    //创建有向图的带有权值的邻接矩阵
    int mat[NUM][NUM];
    for (int i = 0; i < NUM;i++)
    {
        for (int j = 0; j < NUM;j++)
        {
            mat[i][j] = INT_MAX;
        }
    }
    CreateMatrix(mat);
    int visit[NUM] = {0};
    int dist[NUM];
    for (int i = 0; i < NUM;i++)
    {
        dist[i] = INT_MAX;
    }
    int path[NUM] = {0};

    //利用Prim算法求解最小生成树
    //初始源点的dist初始化为0，path初始化为0
    dist[0] = 0;
    path[0] = 0;
    DijkstraSearch(mat,0,visit,dist,path);

    //输出最小生成树的边及相应权值，总权值
    int totalValue = 0;
    for (int i = 1; i < NUM;i++)
    {
        totalValue += dist[i];
        printf("最小生成树的边：<v%d , v%d>",(i+1),(path[i]+1));
        printf(" 权值：%d",dist[i]);
        printf("\n");
    }
    printf("最小生成树的总权值：%d",totalValue);
    printf("\n");

    return 0;
}


//利用二维数组创建有向图的邻接矩阵，带权值
void CreateMatrix(int mat[NUM][NUM])
{
    mat[0][1] = 4;
    mat[0][2] = 2;

    mat[1][0] = 4;
    mat[1][2] = 5;
    mat[1][3] = 5;
    mat[1][4] = 9;

    mat[2][0] = 2;
    mat[2][1] = 5;
    mat[2][3] = 6;

    mat[3][1] = 5;
    mat[3][2] = 6;
    mat[3][4] = 7;
    mat[3][5] = 6;

    mat[4][1] = 9;
    mat[4][3] = 7;
    mat[4][5] = 3;

    mat[5][3] = 6;
    mat[5][4] = 3;
}

//利用Prim算法求解最小生成树
void DijkstraSearch(int mat[NUM][NUM], int i, int visit[NUM], int dist[NUM], int path[NUM])
{
    //初始化
    visit[i] = 1;
    //dist[i] = 0;
    //path[i]=0;

    //访问与顶点i相邻接的未被访问的顶点，获取路径长度，如果小于之前路径长度则替换，并记录路径
    for (int j = 0; j < NUM;j++)
    {
        if (visit[j] == 0 && mat[i][j] != INT_MAX)
        {
            if (mat[i][j]<dist[j])
            {
                dist[j] = mat[i][j];
                path[j] = i;
            }
        }
    }

    //在未被访问过的顶点中寻找路径最短的顶点
    int minDist = -1;
    for (int m = 0;m<NUM;m++)
    {
        if (visit[m] == 0)
        {
            minDist = m;
            break;
        }
    }
    for (int k = minDist + 1; k<NUM; k++)
    {
        if (visit[k] == 0 && dist[k]<dist[minDist])
        {
            minDist = k;
        }

    }
    //如果找到继续寻找到下一个顶点的最短路径（递归）
    if (minDist != -1)
    {
        DijkstraSearch(mat, minDist, visit, dist, path);
    }
}

您好，我是有问必答小助手，您的问题已经有小伙伴帮您解答，感谢您对有问必答的支持与关注！
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632