普里姆算法最小生成树算法.cpp

用普里姆(Prim)算法构造最小生成树,满分作业

#include<stdio.h>
#define NUM 7



struct {
     int   adjvex;  // U集中的顶点序号
     int     lowcost;  // 边的权值
} closedge [7];




typedef struct ArcCell
{
	int adj;             //
	int info;           //弧相关信息的指针
	
}
ArcCell;
typedef ArcCell AdjMatrix[NUM][NUM];
typedef struct
{
	int vexs[NUM];     //顶点向量 
//	int  visited[5];   //初始化的时候全将其设置为0
	AdjMatrix arcs;       //邻接矩阵 
	int vexnum,arcnum;    //图的当前顶点数和弧数 
	int kind;      //图的种类标志
}MGraph;
int visited[NUM]={0,0,0,0,0,0,0};//必须将visited设置为全局变量
MGraph CreateUND()         //创建无向网  用矩阵的存储方式
{
	MGraph G;
	int IncInfo;
	int v1,v2,w;
	int i,j;
	printf("请输入所建立的图的顶点数，弧数：\n");
	scanf("%d,%d,%d",&G.vexnum,&G.arcnum);
	printf("将顶点数组初始化：\n");
	for(i=0;i<G.vexnum;i++)
	{
		scanf("%d",&G.vexs[i]);
	
	}
	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
		{
			G.arcs[i][j].adj=1000;
			G.arcs[i][j].info=0;
		}
	printf("请输入弧的两个顶点和权数：\n");
	for(int k=0;k<G.arcnum;k++)
	{
		scanf("%d,%d,%d",&v1,&v2,&w);
		i=v1-1;
		j=v2-1;
		G.arcs[j][i].adj=G.arcs[i][j].adj=w;
//		if(IncInfo)
		//G.arcs[j][i]=G.arcs[i][j];

	}
	return G;
}
void VisitFunc(int v)
{
	printf("%d\n",v);

}
int FirstAdjVex(MGraph G,int v)
{
	int re=-1;
	for(int i=0;i<G.vexnum;i++)
	{
		if(G.arcs[v-1][i].adj<1000)
		{
			re=i;
			break;
		}
	}
	return re+1;//如果在邻接矩阵中存在返回该定点   

}
int NextAdjVex(MGraph G,int v,int w)
{
	int re=-1;
	for(int i=w;i<G.vexnum;i++)
	{
		if(G.arcs[v-1][i].adj<1000)
		{
			re=i;
			break;
		}
	}
		return re+1;

}
void DFS(MGraph G, int v) 
{
           // 从顶点v出发，深度优先搜索遍历连通图 G
	
	
    visited[v-1]=1;
  
    VisitFunc(v);      // 访问第v 个结点
    for(int w=FirstAdjVex(G,v);w!=0;w=NextAdjVex(G,v,w))
        if (!visited[w-1])  
			DFS(G,w);  
		                            // 对v的尚未访问的邻接顶点w
                                        // 递归调用DFS 
} // DFS



int minimum(MGraph G)
{
	
	int min,j;
//	min=closedge[0].lowcost;
	min=1000;
	for(int i=0;i<G.vexnum;i++)
		if((min>closedge[i].lowcost)&&(closedge[i].lowcost!=0))
		{
			min=closedge[i].lowcost;
			j=i;
		}
	return j;

}
void MiniSpanTree_P(MGraph G, int u) {
                //用普里姆算法从顶点u出发构造网G的最小生成树
	int k;
     k =u-1;
    for (int  j=0; j<G.vexnum; j++ )  //辅助数组初始化
        if (j!=k) 
		{
           closedge[j].adjvex=u;
		closedge[j].lowcost=G.arcs[k][j].adj ;// { u, G.arcs[k][j].adj };
                                                  // {adjvex, lowcost}
		}
    closedge[k].lowcost = 0;          // 初始，U＝{u}
    for (int i=0; i<G.vexnum; i++)
	{//选择其余N-1个顶点

//	k = minimum(closedge);  // 求出加入生成树的下一个顶点(k)
		k=minimum(G);

	printf("%d,%d\n",closedge[k].adjvex, G.vexs[k]); 
                               // 输出生成树上一条边的两个顶点
	 closedge[k].lowcost = 0;    // 第k顶点并入U集
	for (j=0; j<G.vexnum; j++) 
                           // 修改其它顶点的最小边
		if (G.arcs[k][j].adj < closedge[j].lowcost)
                                       // 新顶点并入U后重新选择最小边
		{
			closedge[j].adjvex =  G.vexs[k];
			closedge[j].lowcost=G.arcs[k][j].adj; 
	} 


	}

}
void main()
{
	MGraph G=CreateUND();
	MiniSpanTree_P(G,1);
	printf("遍历为：\n");
	DFS(G,1);

}