keyroad.cpp

这是我在复习备考软件设计师时,写的一个程序,拓朴排序在很多方面都会very important,so i think it will be useful many new hands,so i dec

#include "Queue.h"
#include "stack.h"
//#include <stdio.h>
#define MAX_VERTEX_NUM 10
typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
	int info;
}ArcNode;
typedef struct VNode{
	char data;
	ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct{
	AdjList vertics;
	int indegree[MAX_VERTEX_NUM];
	int vexnum,arcnum;
}ALGraph;
typedef struct WNode{
	int weight;
}WNode;
WNode SavWei[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
int Get_data(ALGraph &G)
{
	int a1,a2,a3,i,j;
	
	FILE *fp;
	fp=fopen("data.txt","r");
	fscanf(fp,"%d %d",&G.vexnum,&G.arcnum);	
	for(i=0;i<G.vexnum;i++)
		fscanf(fp," %c",&G.vertics[i].data);
	for(i=0;i<G.vexnum;i++)
		fscanf(fp,"%d",&G.indegree[i]);

	for(i=0;i<G.vexnum;i++)
		for(j=0;j<G.vexnum;j++)
			SavWei[i][j].weight=0;
		for(i=0;i<G.arcnum;i++)
		{
			fscanf(fp,"%d %d %d",&a1,&a2,&a3);
			SavWei[a1][a2].weight=a3;
		}
		return 1;
}
void Creat(ALGraph &G)
{
	int i,j,k,n,a[10];	
	ArcNode *p1,*p2;
	for(i=0;i<G.vexnum;i++)
	{
		G.vertics[i].firstarc=new ArcNode;
		k=0;
		j=0;
		for(int l=0;l<G.vexnum;l++)
		{
			a[l]=0;
		}
		while(j<G.vexnum)
		{
			if(SavWei[i][j].weight>0)
			{
				a[k]=j;k++;
			}
			j++;
		}
		if(a[0])
		{
			j=a[0];
			G.vertics[i].firstarc->adjvex=j;
			G.vertics[i].firstarc->info=SavWei[i][j].weight;		
			p1=p2=G.vertics[i].firstarc;
			for(n=1;n<k;n++)
			{
				j=a[n];
				p2=new ArcNode;
				p2->adjvex=j;
				p2->info=SavWei[i][j].weight;
				p1->nextarc=p2;
				p1=p2;
			}
			p1->nextarc=0;
		}
		else 
			G.vertics[i].firstarc=0;
	}
}
void Output(ALGraph G)
{
	int i,j;
	for(i=0;i<9;i++)
	{
		cout<<G.vertics[i].data;
		while(G.vertics[i].firstarc)
		{
			j=G.vertics[i].firstarc->adjvex;
			cout<<G.vertics[j].data;
			G.vertics[i].firstarc=G.vertics[i].firstarc->nextarc;
		}
		cout<<endl;
	}
}
int Search(ALGraph G,stack &s,int ve[])
{
	Queue *Q;
	
	int i,j,c;
//	type e;
	TYPE d;
	InitQueue(Q);
	initstack(s);
	for(i=0;i<G.vexnum;i++) ve[i]=0;
	for(i=0;i<G.vexnum;i++)
	{
		j=0;
		while(j<G.vexnum)
		{
			if(G.vertics[j].data!='#'&&!G.indegree[j])
			{
				if(G.vertics[j].firstarc)
				{
					while(G.vertics[j].firstarc->nextarc)
					{	
						c=G.vertics[j].firstarc->adjvex;
						if(ve[c]<ve[j]+G.vertics[j].firstarc->info) 
						{
							ve[c]=ve[j]+G.vertics[j].firstarc->info;
						}
						G.indegree[c]--;
						G.vertics[j].firstarc=G.vertics[j].firstarc->nextarc;
					}
					c=G.vertics[j].firstarc->adjvex;
					if(ve[c]<ve[j]+G.vertics[j].firstarc->info) 
					{
						ve[c]=ve[j]+G.vertics[j].firstarc->info;
					}
					G.indegree[c]--;
				}
				EnQueue(Q,G.vertics[j].data);
				push(s,G.vertics[j].data);
				G.vertics[j].data='#'; 
			}
			else
			j++;
		}
	}
	DeQueue(Q,d);
	cout<<endl;
//	for(i=0;i<G.vexnum;i++)
//	{
//		pop(s,e);
//		cout<<e;			
//	}
	return 1;
}
int KeyRoad(ALGraph G,int ve[],stack &s)
{
	ArcNode *p;	
	int i,j,k,ee,el,weight,vl[10];
	char tag;
	for(i=0;i<G.vexnum;i++)
		vl[i]=ve[G.vexnum-1];
	while(!stackempty(s))
	{
//		pop(s,j);
		for(pop(s,j),p=G.vertics[j].firstarc;p;p=p->nextarc)
		{
			k=p->adjvex;
			weight=p->info;
			if(vl[k]-weight<vl[j]) vl[j]=vl[k]-weight;
		}
	}
		for(j=0;j<G.vexnum;j++)
			for(p=G.vertics[j].firstarc;p;p=p->nextarc)
			{
				k=p->adjvex;
				weight=p->info;
				ee=ve[j];el=vl[k]-weight;
				tag=(ee==el)? '*':' ';
				cout<<j<<" "<<k<<" "<<weight<<" "<<ee<<" "<<el<<" "<<tag<<endl;
//				if(ee==el) cout<<"("<<G.vertics[j].data<<"->"<<G.vertics[k].data<<")"<<"->";
			}
	
	return 1;
}


void main()
{
	ALGraph G;
	int ve[10];
	stack s;
	Get_data(G);
	Creat(G);
	Search(G,s,ve);
	KeyRoad(G,ve,s);
	cout<<endl;
//    Output(G);
}