【数据结构—图】最短路径—Prim算法

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#define MaxSize 50

typedef struct ArcNode{
    int adjvex;
    struct ArcNode *next;
    int weight;
};

struct VNode{
    char value;
    ArcNode *first;
};

struct AdGraph{
    VNode vertices[MaxSize];
    int vexnum,arcnum;
};


/**
    1.算法思想：先圈一个点A，以A点为源点，遍历A到其他剩下点的距离(权值)
    取最小的那个边，然后把这个边连着的点B圈到和A一块儿

    然后将从B点到其他点发射的边的长度与A发射的长度比较，若到对应点长度
    小于A的，就把length[]对应的值换掉，path[]对应的点也改成B.

    然后再在已经换好的lenth[]数组中选取最小的长度，将那个边连着的点C圈到AB里，
    若到对应点长度小于B的，就把length[]对应的值换掉，path[]对应的点也改成C.

    然后再……一直循环，直到最后一个点 被圈入点集中

    注意！:刚开始是已经选了一个点的，所以遍历G.vexnum - 1轮，而不是G.vexnum轮

    2.对数组的解释：
    length[]:保存两个点之间的距离(也就是权值)
    path[]:  保存来到当前顶点的上一个顶点
    visited[]:保存顶点是否被访问过
**/
//最短路径：Prim
void Prim(AdGraph G,int v,int *length,int *visited,int *path){
    for(int i = 0;i < G.vexnum;i++){
        length[i] = INF;
        visited[i] = 0;
        path[i] = -1;
    }
    
    length[v] = 0;
    visited[v] = 1;
    ArcNode *p = G.vertices[v].first;
    while(p){
        length[p->adjvex] = p->weight;
        path[p->adjvex] = v;
        p = p->next;
    }
    //上面是把第一个点的length[],path[]都置好
    //接下来是找G.vexnum - 1趟length[]里面的最小值(也就是圈点)
    int min,minIndex;
    for(int i = 0;i < G.vexnum - 1;i++){
        min = INF;
        for(int j = 0;j < G.vexnum;j++){
            if(visited[j]==0 && length[j] < min){
                min = length[j];
                minIndex = j;
            }
        }    //这个小for是把最小找出来了并且保存了它的下标：minIndex
    //接下来又要将minIndex点进行 与 第一个选出的点v的刚开始那样 的操作：
        visited[minIndex] = 1;
        p = G.vertices[minIndex].first;    //取到minIndex的首指针
        while(p){
            if(visited[p->adjvex]==0 && length[p->adjvex] > p->weight){
                length[p->adjvex] = p->weight;
                path[p->adjvex] = minIndex;
            }
            p = p->next;
        }
    }    //这一趟大循环要做两件事：
            // 1.找出距离最小的那个点
            // 2.以这个点为源点，遍历这个点连接的所有点，比较权值
            //   比length[]里面的值小就替换。
}

/**
总结：
    1.时间复杂度：O(n^2)
    2.空间复杂度：O(1)
    3.适用于 边稠密图
**/