cpp2.cpp

数据结构最小生成树的求法——算法 数据结构可后实习题目

#include <malloc.h>
#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
#include <limits.h>
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
typedef int Status;
typedef int Boolean;
typedef int TElemType;
typedef int VRType;

#define INFINITY INT_MAX        //最大值
#define MAX_TREE_SIZE 100
#define MAX_VERTEX_NUM 20       //最大顶点个数
typedef struct PTNode{
	TElemType data;
	int parent;
}PTNode;
typedef struct{
	PTNode nodes[MAX_TREE_SIZE];
	int r,n;
}PTree;
typedef PTree MFSet;
typedef enum{DG,DN,UDG,UDN} GraphKind;
typedef int AdjMatrix[MAX_VERTEX_NUM][ MAX_VERTEX_NUM];	//弧的邻接矩阵类型
typedef int  ArcCell;			//弧元类型
typedef char  VertexType;		//顶点类型
typedef struct{
	VertexType  vexs[MAX_VERTEX_NUM];		//顶点向量
	AdjMatrix  arcs;					    //邻接矩阵
	int  vexnum, arcnum;					//顶点数和弧数
	GraphKind kind;							//种类标志（无向图取值UDG）
}MGraph;

Status Initial(MFSet &S,int n){
	S.n=n;
	int i;
	for(i=0;i<n;i++){
		S.nodes[i].data=i;
		S.nodes[i].parent=-1;
	}
	return OK;
}

int find_mfset(MFSet S,int i){
	if(i<1||i>S.n) return -1;
	int j;
	for(j=i;S.nodes[j].parent>0;j=S.nodes[j].parent);
	return j;
}

Status merge_mfset(MFSet &S,int i,int j){
	if(i<1||i>S.n||j<1||j>S.n) return ERROR;
	i=find_mfset(S,i);
	j=find_mfset(S,j);
	S.nodes[i].parent=j;
	return OK;
}

int LocateVex(MGraph G,VertexType u){
	int i;
	for(i=0;G.vexs[i]!=NULL;i++){
		if(G.vexs[i]==u) break;
	}
	if(G.vexs[i]!=NULL){
		return i;
	}
	else{
		cout<<"找不到顶点"<<endl;
		return ERROR;
	}
}

Status CreateUDN(MGraph &G){
	cout<<"请输入顶点数和边数:"<<endl;
	cin>>G.vexnum>>G.arcnum;
	int i,j,k,w;
	VertexType v1,v2;
	cout<<"请输入各顶点名称:"<<endl;
	for(i=0;i<G.vexnum;++i) cin>>G.vexs[i];
	for(i=0;i<G.vexnum;++i)
		for(j=0;j<G.vexnum;++j) G.arcs[i][j]=INT_MAX;
	cout<<"请输入各边的顶点和边的权值:"<<endl;
	for(k=0;k<G.arcnum;++k){
		cin>>v1>>v2>>w;
		i=LocateVex(G,v1); j=LocateVex(G,v2);
		G.arcs[i][j]=w;
		G.arcs[j][i]=G.arcs[i][j];
	}
	return OK;
}

int FirstAdjVex(MGraph G,int v){
	int j;
	for(j=0;j<G.vexnum;j++){
		if(G.arcs[v-1][j]!=INT_MAX) break;
	}
	if(j<G.vexnum) return j+1;
	else return -1;
}

int NextAdjVex(MGraph G,int v,int w){
	int j;
	for(j=w;j<G.vexnum;j++){
		if(G.arcs[v-1][j]!=INT_MAX) break;
	}
	if(j<G.vexnum) return j+1;
	else return -1;
}

Boolean visited[INT_MAX];

void DFS(MGraph G,int v){
	int i;
	for(i=0;i<G.vexnum;++i){
		if(!visited[i]==TRUE) visited[i]=FALSE;
	}
	visited[v]=TRUE; cout<<G.vexs[v-1];
	int w;
	for(w=FirstAdjVex(G,v);w!=-1;w=NextAdjVex(G,v,w))
		if(!visited[w]) DFS(G,w);
}

int Mini(MGraph G,int n){
	int i,j,x,xx,y,yy,z,zz; int k=0;
	int a[100];
	int b[100];
	for(i=0;i<G.vexnum;i++){
		for(j=i;j<G.vexnum;j++)
			if(G.arcs[i][j]!=INT_MAX){
				a[k]=i ;
				a[k+G.arcnum]=j;
				k++;
			}
	}
	k=INT_MAX;
	for(i=0;i<G.arcnum;i++){
		for(j=0;j<G.arcnum;j++){
		    x=a[j]; y=a[j+G.arcnum];
			if(x!=-1&&y!=-1&&k>G.arcs[x][y]){
				k=G.arcs[x][y];
		        z=j; zz=j+G.arcnum;
				xx=x; yy=y;
			}
		}
		b[i]=xx; b[i+G.arcnum]=yy;
		a[z]=-1; a[zz]=-1;
		k=INT_MAX;
	}
	return b[n-1];
}

void MiniSpanTree(MGraph G){
	int i,x,y,k,a,b;
	PTree S;
	int n=G.vexnum;
	Initial(S,n);
	for(i=0,k=1;i<G.arcnum;i++,k++){
		x=Mini(G,k); y=Mini(G,k+G.arcnum);
		a=find_mfset(S,x+1); b=find_mfset(S,y+1);
		if(a!=b){
			cout<<G.vexs[x]<<G.vexs[y]<<G.arcs[x][y]<<endl;
			merge_mfset(S,y+1,x+1);
		}
	}
}

void main(){
	MGraph G;
	CreateUDN(G);
	cout<<"最小生成树:"<<endl;
	MiniSpanTree(G);
	cout<<"权值最小的边为:"<<endl;
	int x,y;
	x=Mini(G,1); y=Mini(G,G.arcnum);
	cout<<G.vexs[x]<<G.vexs[y]<<G.arcs[x][y]<<endl;
}