图的邻接矩阵表示方式——最小生成树算法prim&&Kruskal

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define NO 0
#define FALSE 0
#define TRUE 1
#define ERROR -1 

#define INFINITY 200000
#define MAX_VERTEX_NUM 20

typedef int *SetType;
typedef int Status;
typedef int VRType;//图、表顶点关系类型
typedef struct ArcCell
{
    VRType adj;  //权值
}ArcCell;

typedef ArcCell AdjMaxtrix[MAX_VERTEX_NUM+1][MAX_VERTEX_NUM+1];//邻接矩阵
typedef char VertexType_M;//图的顶点类型


typedef struct 
{
    VertexType_M vexs[MAX_VERTEX_NUM+1];//顶点向量
    AdjMaxtrix arcs;
    int vexnum,arcnum;
}MGraph;

//作用非常的重要,主要是为了实现记录每一个结点的前一个结点以及它们之间的权重
typedef struct 
{
    VertexType_M adjvex;//较早加入当前边的端点
    VRType lowcost;//当前边的权值

}Edge;

typedef struct  //定义一个边集用来存储图的所有边信息
{
    int begin,end;
    int weight;
}gEdge;


Status visited[MAX_VERTEX_NUM+1];

Status CreateUDN_M(MGraph *G);

void OutputMGraph(MGraph G);

int LocateVex_M(MGraph G,VertexType_M u);

int MinSpanTree_PRIM(MGraph G,VertexType_M u);

int Minimum(Edge closedge[],int n);

void MinSpanTree_KRUSKAL(MGraph G);


gEdge *CreateEdges(MGraph G);//生成图的排序过的边集数组

int main(int argc,char** argv){
    MGraph G;
    printf("初始化并输出无向网..\n");
    {
        CreateUDN_M(&G);

        OutputMGraph(G);
        printf("\n");
    }
    printf("函数 MinSpanTree_PRIM 测试..\n");
    {
        int total;

        printf("普里姆算法..\n");
        printf("先后加入最小生成树的各结点及其对应的最小边的权值分别为： \n");
        total=MinSpanTree_PRIM(G,'A');
        printf("\n");
        printf("输出最小生成树的总长度为%d\n",total);
        printf("\n");
    }
    printf("函数 MinSpanTree_KRUSKAL 测试..\n");
    {
        printf("克鲁斯卡尔算法..\n");
        printf("最小生成树的各边及其对应的权值分别为：\n");
        MinSpanTree_KRUSKAL(G);
        printf("\n");
    }


    return 0;
}
Status CreateUDN_M(MGraph *G){
    int i,j,k;
    VertexType_M v1,v2;
    VRType w;
    printf("输入顶点数 ");
    scanf("%d",&(G->vexnum));
    printf("输入弧数 ");
    scanf("%d",&(G->arcnum));
    printf("输入各个顶点值 ");
    getchar();
    for(i=1;i<=G->vexnum;i++)
    {
        scanf("%c",&(G->vexs[i]));    
    }
    
    printf("初始化邻接矩阵\n");
    for(i=1;i<=G->vexnum;i++)
    {
        for(j=1;j<=G->vexnum;j++)
            G->arcs[i][j].adj=INFINITY;
    }
    for(k=1;k<=G->arcnum;k++)
    {
        getchar();
        printf("输入相邻结点（添加弧的信息）");
        scanf("%c%c%d",&v1,&v2,&w);
        i=LocateVex_M(*G,v1);
        j=LocateVex_M(*G,v2);
        
        G->arcs[i][j].adj=w;
        G->arcs[j][i]=G->arcs[i][j];
        }


return OK;
}

int LocateVex_M(MGraph G,VertexType_M u)
{
    int i;
    for(i=1;i<=G.vexnum;i++)
    {
        if(G.vexs[i]==u)
            return i;
    }
    return 0;

}


void OutputMGraph(MGraph G){
    int i,j;
    if(!G.vexnum&&!G.arcnum)
        printf("空图（表）！\n");
    else
    {
        printf(" ");
        for(i=1;i<=G.vexnum;i++)
        {
            printf("%3c",G.vexs[i]);
        }
        printf("\n");
        for(i=1;i<=G.vexnum;i++)
        {
            printf("%c",G.vexs[i]);
            for(j=1;j<=G.vexnum;j++)
            {
                if(G.arcs[i][j].adj==INFINITY)
                    printf(" ∞");
                else
                    printf("%3d",G.arcs[i][j]);
            }
            printf("\n");
                
        }
    }
}

/*Prim算法：
本质上是贪心算法，首先输入一个顶点作为起点，提取这个顶点的序号，然后有一个closedge数组来初始化，遍历之后将每个顶点的
前一个访问的结点初始化为u,并且将他们之间的弧的权重直接当成二者之间的权重。然后首先输出一个u.Minmum这个函数主要是用来
求出所有的边中和u相连的弧的权重最小的顶点值(第一个循环的时候),然后输出这个最小的权值以及顶点。并且将这个顶点的标记为
lowcast=0；在后面的访问中就不会用到这个顶点。之后由于这个时候已知的顶点是两个，因此对于所有和第二个结点中连接弧长最小
的顶点，需要改变弧的权值以及前一个顶点的位置。然后第二轮循环进来的时候，同样在Minmum这个函数中实现找出所有哦没有被访问
过的权值最小的顶点，这个时候不需要担心会访问非前面两个邻接点，因为如果不是邻接点，它们的弧的权重将是无穷大，因此肯定会
访问权值最小的结点。然后循环将每一个结点都输出。*/

int MinSpanTree_PRIM(MGraph G,VertexType_M u){
    int i,j,k;
    int total=0;
    Edge closedge[G.vexnum+1];
    k=LocateVex_M(G,u);
    /*将辅助矩阵初始化使每一个结点都标记为前一个结点是u,并且它们之间的距离是无穷大，若是邻接点那么就是adj的值*/
    for(j=1;j<=G.vexnum;j++)
    {
        if(j!=k)
        {
            closedge[j].adjvex=u;  //标记j这个顶点的前一个顶点的信息
            closedge[j].lowcost=G.arcs[k][j].adj;
        }
    }
    closedge[k].lowcost=0; //自己到自己的cost标记为0
    printf("    %c\n", u);
    for(i=1;i<=G.vexnum-1;i++)//总共需要这么多此找出最小边
    {
        k=Minimum(closedge,G.vexnum);
        total+=closedge[k].lowcost;
        printf("%2d,%c\n",closedge[k].lowcost,G.vexs[k]);
        closedge[k].lowcost=0;
        for(j=1;j<=G.vexnum;j++)
        {
            if(G.arcs[k][j].adj<closedge[j].lowcost)
            {
                closedge[j].adjvex=G.vexs[k];
                closedge[j].lowcost=G.arcs[k][j].adj;
            }
        }
    }
    return total;
}

//找到所有和结点邻接的点中权值最小的并且返回j（用来标记最小的值所在的下标）
int Minimum(Edge closedge[],int n){
    int i,j;
    int min=INFINITY;
    i=1;
    j=0;
    for(;i<=n;i++){
        if(closedge[i].lowcost)//从权值不为0的边中选择拥有最小权值的边
        {
            if(closedge[i].lowcost<=min)
            {
                min=closedge[i].lowcost;
                j=i;
            }
        }
    }
    return j;
}

gEdge *CreateEdges(MGraph G){
    int i,j;
    int k=1;
    int EdgeNum=G.arcnum;
    int VertexNum=G.vexnum;
    gEdge temp;
    gEdge *p=(gEdge*)malloc(sizeof(gEdge)*VertexNum*VertexNum);   //之前程序报错 是因为申请的空间不够大，越界了
    
     for(i=1;i<=VertexNum;i++) //边集数组初始化
         for(j=i;j<=VertexNum;j++) //为了避免无向图的每条边被记录两次，只考虑上三角矩阵
             if(G.arcs[i][j].adj!=0&&G.arcs[i][j].adj!=INFINITY){
                 p[k].begin=i;
                 p[k].end=j;
                 p[k].weight=G.arcs[i][j].adj;
                 k++;
             }
            //首个p[i]与后面i+1……最后个依次比较，每一次都将小的放在第i个
    for(i=1;i<EdgeNum;i++)//对边集数组进行选择排序
        for(j=i+1;j<=EdgeNum;j++)
            if(p[i].weight>p[j].weight){
                 // temp.begin=p[i].begin;
                 // temp.end=p[i].end;
                 // temp.weight=p[i].weight;


                temp=p[i];
                p[i]=p[j];
                p[j]=temp;
            }
    return p; //这个时候返回的p是已经从小到大排好序的，并且拥有一共EdgeNumt个大小的数组
}

void MinSpanTree_KRUSKAL(MGraph G){
     int VertexNum=G.vexnum;
     int EdgeNum=G.arcnum;
     gEdge *p=CreateEdges(G);//边数组
     int *index=(int*)malloc(sizeof(int)*VertexNum);
     //index 数组，其元素为连通分量的编号，index[i]=index[j]表示编号为i,j的顶点在一个连通分量里
     int *MSTEdge = (int *)malloc(sizeof(int)*VertexNum); //用来存储已经确定的MST的边的编号共VertexNum-1条边
     int k=1;
    int WeightSum=0;
     int IndexBegin,IndexEnd;
     int i,j,n;



     for(i=1;i<=VertexNum;i++) //初始化所有的index=-1;
         index[i]=-1;

    for(i=1;i<VertexNum;i++)
    {
        for(j=1;j<=EdgeNum;j++)
        {
            if(!(index[p[j].begin]>=0&&index[p[j].end]>=0&&index[p[j].begin]==index[p[j].end])){//找到当前还没有加入到同一个连通分量权值最小的边
                MSTEdge[i]=j;   //将每一个不同的弧复制给MSTEdge 一共有VertexNum条边
                if((index[p[j].begin]==-1)&&(index[p[j].end]==-1))
                    index[p[j].begin]=index[p[j].end]=i;//将两个点之间直接连通
                else if((index[p[j].begin]==-1)&&(index[p[j].end]>=0)){
                    index[p[j].begin]=i;
                    IndexEnd=index[p[j].end];
                    for(n=1;n<=VertexNum;n++)
                        if(index[n]==IndexEnd)
                            index[n]=i;       
                        //如果j这条弧中，有一个结点已经被连通，但是另一个结点还没有被连通，那么这个时候因为这个时候
                        //要加入这一段弧，因此相当于将这两个结点连接起来，因此我们就直接把，和另一个结点连接的所有的相同的结点都幅值为i

                }        
                else  if((index[p[j].end]==-1)&&(index[p[j].begin]>=0))
                {
                    index[p[j].end]=i;
                    IndexBegin=index[p[j].begin];
                    for(n=1;n<=VertexNum;n++)
                    {
                        if(index[n]==IndexBegin)
                            index[n]=i;
                    }

                }
                else   //也就是两个结点都被包含进去了 但是还没有连通 
                {
                    IndexEnd=index[p[j].end];
                    IndexBegin=index[p[j].begin];
                    for(n=1;n<=VertexNum;n++)
                    {
                        if(index[n]==IndexBegin||index[n]==IndexEnd)
                            index[n]=i;
                    }

                }
                break;  
                //里面执行完一次之后直接跳出循环，i进入下一条边，而j仍然从0开始，而之前幅值过的边不会再进去
                //因此能够保证进去的边第一次，而对于新的边中如果两个结点已经是同一个集合中的元素，也不会再进去

            }
        }
    }




     printf("MTS的边为：\n");
     for(i=1;i<VertexNum;i++){
         printf("%c--%c\n",G.vexs[p[MSTEdge[i]].begin],G.vexs[p[MSTEdge[i]].end]);
         WeightSum+=p[MSTEdge[i]].weight;
     }
    printf("MST的值为：%d\n",WeightSum);

}

 

 

参考 http://www.cnblogs.com/kangjianwei101/p/5222014.html

http://blog.csdn.net/u014488381/article/details/41447229