数据结构课程设计 最小生成树，拓扑排序以及最短路径

通信网络的架设问题

【问题描述】

若要在n（≥10）个城市之间建设通信网络，只需要架设n-1条线路即可，如何以最低的经济代价建设这个通信网，是一个网的最小生成树问题。

【基本要求】

（1）利用二种方法（Prim算法和克鲁斯卡尔（Kruskual）生成网中的最小生成树。

（2）求出任意两个城市之间通信的最短距离。

（3）将n个城市设计为一个DAG图，求出一组拓扑排序序列和关键路径。

#include<stdio.h>
#include<malloc.h>
#define inf 999
#define MVNum 100

//首先创建邻接矩阵
typedef struct amgraph{
	int vexnum,edgenum;//图中顶点和边
	int juzhen[20][20];// 邻矩阵
	int vexs[20];//顶点表 
}amgraph; 




int topo[20];        //定义拓扑排序数组 
//创建邻接表结构
typedef struct ArcNode{       //边表 
 int adjvex;//该边所指向的顶点位置 
 struct ArcNode *nextarc;//指向下一条边的指针 
 char info;    //和边相关信息，权值 
}ArcNode;


typedef struct VNode{       //表头结点表 
 char data;
 ArcNode *firstarc;
}VNode,AdjList[MVNum];


typedef struct{         //邻接表，带权有向图 
 AdjList vertices;
 int vexnum,arcnum;
}ALGraph;
//拓扑排序创建链栈，以度为零作为判断条件 

typedef struct StackLink{
 int data;
 struct StackLink *next;
}StackLink,*StackNode;

//栈的基本操作 
int InitStack(StackNode &S){
 S = NULL;
 return 1;
}
int Push(StackNode &S,int e){
 StackNode p;
 p = (StackLink*)malloc(sizeof(StackLink));
 p->data = e;
 p->next = S;
 S = p;
 return 1;
}
int Pop(StackNode &S,int &e){
 StackNode p;
 p = (StackLink*)malloc(sizeof(StackLink));
 if(S==NULL)
  return  0;
 e = S->data;
 p = S;      //用P临时存放栈顶元素
 S = S->next; 
 free(p);
 return 1; 
}
int GetTop(StackNode S){
 if(S!=NULL)
  return S->data;
}
int StackEmpty(StackNode S){
 if(S!=NULL)
  return 0;
 else 
  return 1;
}
int LocateVex(ALGraph G,char c){
 int i;
 for(i=0;i<G.vexnum;++i){
  if(c==G.vertices[i].data)
   return i;
 }
 return -1;
}
//邻接表的创建 
int CreateDAG(ALGraph &G){
 int i,j,k,weight;
 char v1,v2;
 ArcNode* p;
 printf("[请输入总顶点与总边数]:\n>>>");
 scanf("%d %d",&G.vexnum,&G.arcnum);
 for(i=0;i<G.vexnum;i++){         //输入各点，构造表头结点表 
  printf("\n[请依次输入顶点信息]:\n>>>");
  getchar();
  scanf("%c",&G.vertices[i].data);
  G.vertices[i].firstarc = NULL;
 }
 for(k=0;k<G.arcnum;k++){
  printf("\n[请输入各边及权值构造邻接表]:\n>>>");
  getchar();
  scanf("%c %c %d",&v1,&v2,&weight);
  i = LocateVex(G,v1);
  j = LocateVex(G,v2);
  p = (ArcNode*)malloc(sizeof(ArcNode));
  p->adjvex = j;
  p->info = weight;
  p->nextarc = G.vertices[i].firstarc;
  G.vertices[i].firstarc = p;
 }
 return  1;
}

void FindInDegree(ALGraph G,int indegree[]){//遍历邻接表求出入度 并放入indegree数组中 
 ArcNode *p;
 int i;
 for(i=0;i<G.vexnum;i++)    //入度初始化为零 
  indegree[i] = 0;
 for(i=0;i<G.vexnum;i++){   //遍历邻接表 
  p = G.vertices[i].firstarc;
  while(p!=NULL){
   indegree[p->adjvex]++;
   p = p->nextarc;
  }
 }
}

int TopologicalSort(ALGraph G,int topo[]){
 int i;
 ArcNode *p; 
 StackNode S;        //定义链栈 
 int indegree[MVNum];
 FindInDegree(G,indegree);     //求出各顶点入度，存入数组indegree中
 
 InitStack(S);        
 for(i=0;i<G.vexnum;i++){
  if(indegree[i]==0)
   Push(S,i);       //入度为零，则入栈 
 }
 int m=0;
 while(!StackEmpty(S)){
  Pop(S,i);        //将栈顶顶点vi出栈 
  topo[m] = i;       //将vi保存在拓扑序列数组topo，便于后序的输出 
  m++;         //对输出顶点计数 
  p=G.vertices[i].firstarc; 
     
  while(p!=NULL){
   int k = p->adjvex;     //vk为vi的邻接点 
   indegree[k]--;      //vi的每个邻接点入度减1 
   if(indegree[k]==0)
    Push(S,k);      //若入度为0则入栈 
   p = p->nextarc;      // 
  }
  
 }
 if(m<G.vexnum)        //通过m和顶点总数判断有无回路 
  return 0;
 else
  return 1;
}


int CriticalPath(ALGraph G){
 ArcNode *p;
 int ve[MVNum];     //最早发生时间 
 int vl[MVNum];     //最迟发生时间 
 int i,j,k,e,l;
 if(!TopologicalSort(G,topo))
  return 0;    
 int n = G.vexnum;    //n为顶点个数
 
 for(i=0;i<n;i++)
  ve[i] = 0;     //个每个事件的最早发生时间置初值0
 
 
 for(i=0;i<n;i++){
  k=topo[i];     //取得拓扑排序序列中顶点序号k 
  p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点 
  while(p!=NULL){    //依次更新k的所有邻接顶点的最早发生时间 
   j = p->adjvex;   //j为邻接顶点的序号 
   if(ve[j]<ve[k]+p->info) //更新顶点j的最早发生时间ve[j] 
    ve[j] = ve[k]+p->info;
   p = p->nextarc;   //p指向k的下一个邻接顶点 
  }
 }
 for(i=0;i<n;i++)    //给每个事件的最迟发生时间置初值ve[n-1] 
  vl[i] = ve[n-1];
 
 for(i=n-1;i>=0;i--){//按逆拓扑次序求每个事件最迟发生时间
  k = topo[i];   //i已调整，逆序 
  p = G.vertices[k].firstarc; //p指向k的第一个邻接顶点
  while(p!=NULL){    //根据k的邻接点，更新k的最迟发生时间 
   j = p->adjvex;   //j为邻接顶点的序号 
   if(vl[k]>vl[j]-p->info) //更新顶点k的最早发生时间vl[k] 
    vl[k] = vl[j]-p->info;
   p = p->nextarc;   //p指向k的下一个邻接顶点 
  }
 }
 
 printf("关键路径如下:\n\n");
 for(i=0;i<n;i++){
  p = G.vertices[i].firstarc; //p指向k的第一个邻接顶点
  while(p!=NULL){
   j = p->adjvex;   //j为i的邻接顶点的序号 
   e = ve[i];    //最早开始时间 
   l = vl[j]-p->info;  //计算活动<vi,vj>的最迟开始时间 
   if(e==l)     //若为关键活动则输出<vi,vj> 
    printf("<%c,%c>",G.vertices[i].data,G.vertices[j].data);
   p = p->nextarc;   //p指向i的下一个邻接顶点 
  } 
 }
 
 return 1;
}



void creat(amgraph &g){//邻接矩阵的创建 
printf("请输入城市数目和线路数目");
scanf("%d %d",&g.vexnum ,&g.edgenum);
for(int i=0;i<g.vexnum;i++){
	g.vexs[i]=i;
}	
for(int i=0;i<g.vexnum;i++){
	for(int j=0;j<g.vexnum;j++){
		g.juzhen[i][j]=inf;
		if(i==j) g.juzhen[i][j]=0;
	}
} 
printf("请输城市的信息和线路的权值");
printf("\n"); 
for(int i=0;i<g.edgenum;i++){
	int x,y,w;
	scanf("%d%d%d",&x,&y,&w);
	g.juzhen[x][y]=w;
	g.juzhen[y][x]=w;
} 
}

int GetRoot(int v[],int p){
	while(p!=v[p]){//依据根节点的数组下标和 里面的值相同来找到根节点 
		p=v[p];//若两个元素的根节点相同则属于同一颗树 
	}
}


 
void Kruskal(amgraph g){//卡鲁索算法 
	int v[g.vexnum];
	for(int i=0;i<g.vexnum;i++) v[i]=i;//初始化并查集 
	int sum=0;
	for(int q=0;q<g.vexnum-1;q++){//连通一个图需要n-1条边，(n为顶点数) 
	int x,y;
	int  min=inf;
	for(int i=0;i<g.vexnum;i++){	
		for(int j=0;j<g.vexnum;j++){ 	
			if(g.juzhen[i][j] <min&&g.juzhen[i][j]>0&&GetRoot(v,i)!=GetRoot(v,j)){//getroot不相等说明不形成回路 
				min=g.juzhen[i][j];                                          
				x=i;
				y=j;
 
			}
		} 
	}
				printf("[%d %d]\n",x,y); 
			
				g.juzhen[x][y]=0;//将这条边置零，以便选出次小边 
				g.juzhen[y][x]=0;//无向图 
				v[y]=x;//将两个结点挂在一棵树上
	}

} 




void prim(amgraph g,int v){//普利姆算法 
	int lowcost[20];
	int min;
	int closest[20],i,j,k;
	for(i=0;i<g.vexnum;i++){
		lowcost[i]=g.juzhen[v][i];
		closest[i]=v;
	}
	for(i=1;i<g.vexnum;i++){
	min=inf;
	for(j=0;j<g.vexnum;j++)//通过比较，找出到该顶点的最小权值，但只能选中有通路部分 
		if(lowcost[j]!=0 && lowcost[j]<min){
			min=lowcost[j];
			k=j;
		}	
		printf("[%d %d]\n",closest[k],k);
		lowcost[k]=0;//此处置零表示顶点k已经加入到了集合中 
		for(j=0;j<g.vexnum;j++)
			if(g.juzhen[k][j]!=0&&g.juzhen[k][j]<lowcost[j]){
				lowcost[j]=g.juzhen[k][j];
				closest[j]=k;
			}
	}
} 





void dispallpath(amgraph g,int a[][20],int path[][20]){
	int i,j,k,s;
	int apath[20],d;//apath中存放着一条最短路径 
	for(i=0;i<g.vexnum;i++)
		for(j=0;j<g.vexnum;j++){
			if(a[i][j]!=inf &&i!=j){//判断条件，i，j之间存在路径 
				printf("顶点%d到%d的最短路径长度：%d路径：",i,j,a[i][j]);
				k=path[i][j];
				d=0;apath[d]=j;
				while(k!=-1&&k!=i){
					d++;
					apath[d]=k;
					k=path[i][k];
				}	
				d++;
				apath[d]=i;
				printf("%d",apath[d]);
				for(s=d-1;s>=0;s--)
					printf("->%d",apath[s]);
					printf("\n");
						}
		}
		
}

void Floyd(amgraph g){//关键在于建立两个数组以及数组如何更新 
	int a[20][20];
	int path[20][20];
	int i,j,k;
	for( i=0;i<g.vexnum;i++)//求出每对顶点的最短路径 
		for(j=0;j<g.vexnum;j++){
			a[i][j]=g.juzhen[i][j];
				if(i!=j&& g.juzhen[i][j] <inf)
		 	path[i][j]=i;//要是顶点之间有边则置为i 
				else
			path[i][j]==-1;//顶点之间没有边则置为-1 
		}
	for(k=0;k<g.vexnum;k++){
		for(i=0;i<g.vexnum;i++)
			for(j=0;j<g.vexnum;j++)//遍历两个数组 
				if(a[i][j]>a[i][k]+a[k][j]){
					a[i][j]=a[i][k]+a[k][j];
					path[i][j]=path[k][j];//修改最短路径为经过k 
				}
	}
	dispallpath(g,a,path);//输出最短路径的长度 
} 




int main(){
int a,b;
amgraph g;
creat(g);
printf("Kruskal生成的最小生成树为\n"); 
Kruskal(g);
printf("prim生成的最小生成树为\n");	
prim(g,0);
Floyd(g);
int i,user;
 ALGraph G;
  scanf("%d",&user);
   CreateDAG(G);
  TopologicalSort(G,topo);
   printf("拓扑排序结果如下:\n");
   for(i=0;i<G.vexnum;i++)
    printf("%c->",G.vertices[topo[i]].data);
    CriticalPath(G);
   
   
  
 

}
	
	

测试用例以及结果显示 (已在DEV C++等编译器上通过）