图--最小生成树-PRIM算法

最小生成树：两个算法 1）普里姆（Prim） 2）克鲁斯卡尔（kruskal）

1）Prim
假设N={V,{E}}是连通网，TE是N上最小生成树中的边的集合。
算法从U={u0}(u0属于V)开始TE={}开始，重复执行下述操作：
在所有u属于U，v属于V-U的边(u,v)属于E中找一条代价最小的边(u0,v0)并入集合TE，同时v0并入U，直至U=V为止。
在TE中必有n-1条边，则T=(V,{TE})为N的最小生成树。

1、使用辅助数组closedge记录从U中到V-U中代价最小的边。(即V-U中的结点到U中哪个结点的代价最小)
2、V表示图的全部结点的集合，当有结点已经用于生成最小生成树后把结点加入U中，cloaedge的lowcost为0表示结点在U中
3、图用邻接表存储时，要注意在每一次将节点加入U过程后对closedge中lowcost的更新。要设置一个标志，表示在当前过程该节点的lowcost是否已经被更新过，如果已经被更新过，则不再被更新。

实现：

 #include <stdio.h>
#include <stdlib.h>
//图的邻接表存储表示
#define MAX_VERTEX_NUM 20
#define INF INT_MAX
typedef int InfoType;
typedef int VertexType;
typedef struct ArcNode{
	int adjvex; //邻接点序号
	int value; //表示边的权值
	struct ArcNode* nexttarc; //下一条边的顶点
	InfoType *info;
};
typedef struct VNode{
	VertexType data;    //顶点信息 
	ArcNode *firsttarc;  //指向第一条边节点
}VNode, AdjList[MAX_VERTEX_NUM];  //单链表的头结点类型

typedef struct{
	AdjList Vertices;   //单链表头结点数组
	int vexnum, arcnum;  //实际的顶点数vexnum 边数arcnum
}ALGraph;

int visited[MAX_VERTEX_NUM];
int finished[MAX_VERTEX_NUM];
int count;
#define LENGTH 6
#define ARCLENGTH 20

typedef struct Minimum{
	VertexType adjvex;
	int lowcost;
	int flag;
}Minimum,closedge[MAX_VERTEX_NUM];

//int graph[6][6] = {
//	INF, 5, INF, 7, INF, INF,
//	INF, INF, 4, INF, INF, INF,
//	8, INF, INF, INF, INF, 9,
//	INF, INF, 5, INF, INF, 6,
//	INF, INF, INF, 5, INF, INF,
//	3, INF, INF, INF, 1, INF
//};

int graph[LENGTH][LENGTH] = {
	INF, 6, 1, 5, INF, INF,
	6, INF, 5, INF, 3, 0,
	1, 5, INF, 5, 6, 4,
	5, INF, 5, INF, INF, 2,
	INF, 3, 6, INF, INF, 6,
	INF, INF, 4, 2, 6, INF
};

//确定节点u在图中的编号
int LocateVex(ALGraph G, VertexType u){
	int i;
	for (i = 0; i < G.vexnum; i++){
		if (G.Vertices[i].data == u)
			return i;
	}
	return -1;
}
int FirstAdjVex(ALGraph G, VertexType u){
	return LocateVex(G, G.Vertices[u].firsttarc->adjvex);
}
int NextAdjVex(ALGraph G, VertexType v, VertexType w){
	return 1;
}

/*寻找v中节点到u各节点间最小的权值，返回节点的编号*/
int minimum(ALGraph G, closedge minedge){
	int i, j, first, min;
	for (i = 0; i < G.vexnum; i++){
		if (minedge[i].lowcost != 0){
			min = minedge[i].lowcost;
			first = i;
			break;
		}
	}
	j = i;
	for (i = first; i < G.vexnum; i++){
		if (min > minedge[i].lowcost && minedge[i].lowcost != 0){
			min = minedge[i].lowcost;
			j = i;
		}
	}

	return j;
}
/*最小生成树算法，closedge[i]==0 表示i在集合U中*/
void MiniSpanTree_PRIM(ALGraph G, VertexType u){
	ArcNode *p ;
	int k = LocateVex(G, u);
	int j = 0;
	closedge minedge;
	int i;
	int index;
	for (i = 0; i < G.vexnum; i++){
		minedge[i].flag = 0; //将访问标志初始化为0 
	}
	for (i = 0; i < G.vexnum; i++){
		if (i != k){
			minedge[i].adjvex = u;
			p = G.Vertices[i].firsttarc;  

			while (p){
				index = LocateVex(G, p->adjvex); //找到邻接节点对应的索引
				if ( index == k){ //p->adjvex==k说明编号为i的结点与编号为k的结点间有弧连接，需要把minedge的lowcost修改为弧上的权值
					minedge[i].lowcost = p->value;
					minedge[i].flag = 1; //设置标志，表面已经更新过权值
				}
				else if (minedge[i].flag == 0){
					minedge[i].lowcost = INF;
				}
				p = p->nexttarc;
			}
		}
		minedge[k].adjvex = G.Vertices[k].data;
		minedge[k].lowcost = 0;
	}

	for (int i = 1; i < G.vexnum; ++i){
		k = minimum(G, minedge);
		printf("(v%d-->v%d):%d\n", minedge[k].adjvex, G.Vertices[k].data ,minedge[k].lowcost);
		minedge[k].lowcost = 0;//将节点k加入到U中
		for (p = G.Vertices[k].firsttarc; p != NULL; p = p->nexttarc){
			index = LocateVex(G, p->adjvex);//找到邻接节点对应的索引
			if (minedge[index].lowcost != 0){ //判断，如果结点不在U中，那么肯定在V-U中，则更新其与当前结点的权值
				minedge[index].lowcost = p->value;
				minedge[index].adjvex = G.Vertices[k].data;
			}
		}
	}

}
/*深度优先搜索遍历DFS*/
void DFS(ALGraph G, int v){
	visited[v] = true;
	printf("v%d-->", G.Vertices[v].data);

	ArcNode *p = G.Vertices[v].firsttarc;
	int k = LocateVex(G, p->adjvex);
	while (p != NULL){
		if (!visited[k]){
			DFS(G, k);
		}
		p = p->nexttarc;
	}

}
void DFSTraverse(ALGraph G){
	for (int v = 0; v < G.vexnum; ++ v){
		visited[v] = false;
	}
	for (int v = 0; v < G.vexnum; ++ v){
		if (!visited[v]){
			DFS(G, v);
		}
	}
}

void CreateGraph(ALGraph &G){
	G.vexnum = LENGTH;
	G.arcnum = ARCLENGTH;
	//初始化顶点的信息
	for (int i = 0; i < G.vexnum; i++){
		G.Vertices[i].data = i+1;
		G.Vertices[i].firsttarc = NULL;
	}
	for (int i = 0; i < LENGTH; i++){
		for (int j = LENGTH - 1; j >= 0; j--){
			if (graph[i][j] != INF){
				ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex = j + 1;
				p->value = graph[i][j];
				p->nexttarc = G.Vertices[i].firsttarc;
				G.Vertices[i].firsttarc = p;
			}
		}
	}
}
void DisplayerGraph(ALGraph &G){
	int i = 0;
	ArcNode *p;
	for (i = 0; i < G.vexnum; i++){
		printf("顶点[V%d]的邻接边 ", G.Vertices[i].data);
		p = G.Vertices[i].firsttarc;
		while (p){
			printf("-->(%d,%d)", p->adjvex, p->value);
			p = p->nexttarc;
		}
		printf("-->(^)\n");
	}
}

int main(){
	ALGraph  *G;
	G = (ALGraph*)malloc(sizeof(ALGraph));
	CreateGraph(*G);
	DisplayerGraph(*G);
	printf("深度优先搜索：\n");
	DFSTraverse(*G);
	printf("^\n最小生成树Prim算法实现\n");
	MiniSpanTree_PRIM(*G, (*G).Vertices[0].data);
	return 1;
}