图的演示.cpp

这是一个小小的程序

  scanf("%d",&n); 
  p->vexnum=n;
  printf("请输入边数:");
 scanf("%d",&m);
  p->arcnum=m;
  for(i=0;i<n;++i)
   for(j=0;j<n;++j)
    if(i==j)
     p->arcs[i][j]=0;
    else
     p->arcs[i][j]=MAX;//邻接矩阵初始化

 for(i=1;i<=m;i++)
 {
   printf("请输入第%d条边的顶点序号v（0<=v<=%d）及该边权值：",i,n);
   scanf("%d %d %d",&v1,&v2,&w);
   if(v1>=0&&v1<n&&v2>=0&&v2<n)
   {
	 p->arcs[v1][v2]=w;
  	 p->arcs[v2][v1]=w;
   }//
 }//for
}


int prim(MGraph G,int v)
{//用prim算法从序号为v的顶点出发构造最小生成树
	//并返回权值和
	int i,j,k,min,c=0;
	int lowcost[MAXNode],closest[MAXNode];
	for(i=0;i<G.vexnum;++i)
	{//对每一个结点
		closest[i]=v;//初值最近点
		lowcost[i]=G.arcs[v][i];
	}
 
 for(i=0;i<G.vexnum-1;i++)
 {
	min=MAX;
	for(j=0;j<G.vexnum;++j)
	  //在余下的顶点中找出最近的那个，并用k记下其序号
	if(lowcost[j]!=0&&lowcost[j]<min)
	{
		min=lowcost[j];
		k=j;
	}

	printf("v%d-v%d\t%d\n",closest[k],k,min);
	c+=min;

	lowcost[k]=0;//将此点归并
	for(j=0;j<G.vexnum;++j)
	 if(G.arcs[k][j]!=0&&G.arcs[k][j]<lowcost[j])
	 {
		lowcost[j]=G.arcs[k][j];
		closest[j]=k;
	 }

 }
 return c;
}

/*
int Kruskal(Graph G)
{//用Kruskal算法从序号为0的顶点出发构造最小生成树
	//并返回权值和
int i,j,min,c=0,k;
for(i=0;i<G.vexnum;i++)
{//对每一个结点
	min=MAX;
	for(j=0;j<G.vexnum;++j)
	{	if(i!=j&&G.arcs[i][j]<min)
			min=G.arcs[i][j];
			k=j;
	}
			G.arcs[k][i]=MAX;
			printf("v%d-v%d %d\n",i,k,min);
			c+=min;
	}
	return c;

}*/


void Prim()
{
 int cost;
 MGraph G;
 CreateMGraph(&G);
 printf("prim得的最小生成树为:\n");
 printf("边\t 权值\t\n");
 cost=prim(G,0);
 printf("Cost :   %d\n",cost);
}


typedef struct Vexnode{ 
	int id;				//结点的出度
	arcnode *firstarc;	//结点邻边
}Topovexnode,TAdjlist[100];  //顶点结点

typedef struct{
	TAdjlist g;
	int w[MAX][MAX];
	int arcnum,vexnum;
}TopoGraph;//图存储结构

typedef struct{
	int data[MAX];
	int top;
}Topostack;


void InitTStack(Topostack &s){
	//初始化栈
	int i;
	for(i=0;i<MAX;i++)
		s.data[i]=0;
	s.top=0;
}//SqstackInit()


void TPush(Topostack &s,int i){
	// 把元素x压入栈，使其成为新的栈顶元素 
	if(s.top> MAX )
		printf("栈已满!");
	s.data[s.top++]=i;  
}//SqstackPush


int TStackEmpty(Topostack s){
	//判断栈是否为空,若是空返回1;
	if(s.top==0)
		return 1;
	else 
		return 0;
}//SqstackEmpty


void TPop(Topostack &s,int &i)
{
	//把栈顶元素弹出
	if(s.top!=0)
		i=s.data[--s.top];
}//SqstackPop

void CreatTGraph(TopoGraph &G)
{ //创建邻接表存储图G
	int i,j,e; 
	arcnode *p; 
	printf("请输入图中结点个数v（0<v<20）：\n"); 
	scanf("\n%d",&G.vexnum); 
	for(i=0;i<G.vexnum;i++)
	{ 
		G.g[i].firstarc=NULL; 
		G.g[i].id=0;
	}		//初始化图的邻接表
	
	printf("请输入图中边的个数b（0<b<20）："); 
	scanf("%d",&G.arcnum); 
	for(i=0;i<G.vexnum;++i)
		for(j=0;j<G.vexnum;++j)
			G.w[i][j]=0;
		for(e=0;e<G.arcnum;e++)
		{ 
			printf("请输入第%d条边（Vi->Vj）的两顶点序号i,j及该边权值:",e+1);
			scanf("%d %d %d",&i,&j,&G.w[i][j]);
			if((i>=0)&&(i<G.vexnum)&&(j>=0)&&(j<G.vexnum))
			{ 
				p=(arcnode*)malloc(sizeof(arcnode)); 
				p->adjvex=j; 
				p->next=G.g[i].firstarc; 
				G.g[i].firstarc=p; 
				++G.g[j].id;
			}
		}
	
} 


void TopuSort(TopoGraph G)
{//有向图G采用邻接表存储
	//若图中G没有环,则输出的顶点的一个拓扑排序
	int i,j=0,count=0; 
	arcnode *p=NULL; 
	Topostack s;
	InitTStack(s);		//建立0入度顶点栈
	for(i=0;i<G.vexnum;i++) 
		if(G.g[i].id==0) TPush(s,i);  //将0入度顶点入栈
		
		while(!TStackEmpty(s))
		{ 
			TPop(s,i); 
			printf(" v%d ",i+1); //输出0入度顶点
			count++; 
			p=G.g[i].firstarc; 
			while(p)
			{ 
				j=p->adjvex; G.g[j].id--;	 //将以vj为头的点入度减1			
				if(G.g[j].id==0) TPush(s,j);		//将0入度顶点入栈
				p=p->next;
			}
		}
		if(count<G.vexnum) printf("图中有环!!!\n");
} 


int TopologicalOrder(TopoGraph G,Topostack &T,	int ve[MAX])
{// 
	Topostack s;			// 入度为零的栈
	int count=0,i,j;
	arcnode *p;
	InitTStack(s);
	for(i=0;i<G.vexnum;i++) 
	{    
		ve[i]=0;
		if(G.g[i].id==0) TPush(s,i);
	}
	
	while(!TStackEmpty(s))
	{ 
		TPop(s,i);
		TPush(T,i);
		count++; 
	
	for(p=G.g[i].firstarc;p; p=p->next)
		{ 
			j=p->adjvex; 
			if(--G.g[j].id==0) TPush(s,j); 
			if(ve[i]+ G.w[i][j]>ve[j])ve[j]=ve[i]+G.w[i][j];		
			
		}
	}
	
	if(count<G.vexnum) return 0;
	else 
		return 1;
	
} 



void CriticalPath(TopoGraph G)
{//G为有向网，输出其关键活动
	Topostack T;
	InitTStack(T);
	int i,j,e[MAX],el;
	for(i=0;i<MAX;i++)
		e[i]=0;
	int vl[MAX],ve[MAX];
	arcnode *p;
	if(TopologicalOrder(G,T,ve))
	{
	
		for(i=0;i<G.vexnum;i++)
			vl[i]=ve[G.vexnum-1];
		while(!TStackEmpty(T))
			for(TPop(T,i),p=G.g[i].firstarc;p;p=p->next)
			{
				j=p->adjvex;
				
				if(vl[j]-G.w[i][j]<vl[i])vl[i]=vl[j]-G.w[i][j];
			}//for				
			for(i=0;i<G.vexnum;++i)
			{	
			for(p=G.g[i].firstarc;p;p=p->next)
				{
					j=p->adjvex;
					el=vl[j]-G.w[i][j];
					if(ve[i]==el)
						e[i]=1;
				}
			}
			for(i=0;i<G.vexnum;++i)
				if(e[i])
					printf("关键活动为：v%d\n",i+1);
				printf("关键活动为：v%d\n",G.vexnum);

	}//if

	else printf("ERROR!\n");
}


void main0()
{
	int ch;
	TopoGraph G;
	printf("\n\n\n");
	printf("--------------------------------0.退出---------------------------------\n");
	printf("--------------------------------1.先建立图-----------------------------\n");
	printf("--------------------------------2.拓扑排序及关键路径-------------------\n");
	printf("--------------------------------3.关键活动-----------------------------\n");
	printf("请选择操作：\n");
	scanf("%d",&ch);
	while(ch!=0)
	{
		switch(ch)
		{
		case 1:
			CreatTGraph(G); break;//建立图的邻接表
		case 2:	
			printf("拓扑排序后结点顺序为\n");
			TopuSort(G);break;
		case 3:
			CriticalPath(G);break;
		default:printf("请重新选择操作：\n");
		}
	printf("\n\n\n");
	printf("--------------------------------0.退出---------------------------------\n");
	printf("--------------------------------1.先建立图-----------------------------\n");
	printf("--------------------------------2.拓扑排序及关键路---------------------\n");
	printf("--------------------------------3.关键活动-----------------------------\n");
	printf("\n请选择操作：\n");
	scanf("%d",&ch);
	}
}


typedef struct {
	int adjvex;//最短路径所经过的点
	int lowcost;//S集的点到该点的最短路径权值
}closedge[MAX];//辅助数组

void DIJ(int g[MAX][MAX],int k,int n)
{//g[][]为图的邻接矩阵，用Dijkstra算法求有向图G的
	//从顶点vk到其他顶点的最短距离
	closedge D;
	int i,j,min,p;
	for(i=0;i<n;i++)
		if(i!=k)
		{
			D[i].adjvex=k;
			D[i].lowcost=g[k][i];
		}					//初始化辅助数组
	D[k].lowcost=0;	//初始化顶点k属于S集

	for(i=0;i<n;i++)//开始主循环是每次所得次短路经的点加入S集
	{
		p=0;min=INFINITE;
		for(j=0;j<n;j++)
			if(D[j].lowcost!=0&&D[j].lowcost<min)
			{
				min=D[j].lowcost;
				p=j;
			}	//找出次短路经的下个结点
		if(min!=INFINITE)
		printf("最短路径为v%d->v%d  该路径权值为%d\n",D[p].adjvex,p,min);
		D[p].lowcost=0;       //点加入S集

		for(j=0;j<n;j++)
			if(g[p][j]<D[j].lowcost)
			{
				D[j].lowcost=g[p][j];
				D[j].adjvex=p;
			}	//修改辅助数组
	}
}



void mainshort()
{//主函数
	int i,j,k,n;
	int g[MAX][MAX];
	printf("请输入图中结点的个数：");
	scanf("%d",&n);

	for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		{
			printf("请输入边v%d->v%d的权值（若不存在边请输入100,自回边输入0）\n",i+1,j+1);
			scanf("%d",&g[i][j]);
		}	
		
		printf("\n请输入源点序号k（0<=k<%d,当输入值为%d时退出！）\n",n,n);
		scanf("%d",&k);
		while(k!=n)
		{   DIJ(g,k,n);
			printf("\n请输入源点序号k（0<=k<%d,当输入值为%d时退出！）\n",n,n);
			scanf("%d",&k);
			
		}
}




void main1()
{	
	HTree t;
	int choose;
	BiTree T;	
	printf("	\n\n\n				\n");
	printf("----------------------------欢迎观看二叉树的演示系统!---------------------\n");
	printf("----------------------------1、用二叉链表存储二叉树------------------------\n");
	printf("----------------------------2、先序遍历二叉树------------------------------\n");
	printf("----------------------------3、中序遍历二叉树------------------------------\n");
	printf("----------------------------4、后序遍历二叉树------------------------------\n");
	printf("----------------------------5、哈夫曼编码----------------------------------\n");
	printf("----------------------------0、退出！--------------------------------------\n");
	printf("\n请输入你的选择:\n");
	scanf("%d",&choose);
	while(choose){
		
		switch(choose)
		{
		case 0:break;
		case 1: printf("依次按先序遍历顺序输入各点值：（结点不存在用0代替）\n");
			CreatBitree(T);break;
		case 2:printf("先序遍历结果为：\n");PreOrderTraverse(T);break;
		case 3:printf("中序遍历结果为：\n");InOrderTraverse(T);break;
		case 4:printf("后序遍历结果为：\n");PostOrderTraverse(T);break;
		case 5: haffman(t);break;
		default:printf("请重新输入你的选择:");;
			
		}
		printf("\n\n\n				\n");
		printf("----------------------------2、先序遍历二叉树------------------------------\n");
		printf("----------------------------3、中序遍历二叉树------------------------------\n");
		printf("----------------------------4、后序遍历二叉树------------------------------\n");
		printf("----------------------------5、哈夫曼编码----------------------------------\n");
		printf("----------------------------0、退出！--------------------------------------\n");
		printf("\n请输入你的选择:\n");
		scanf("%d",&choose);
	}
	
}







 void main2()
 {
	 int ch;
	 Graph G;
	 printf("	\n\n\n					\n");
	 printf("----------------------------欢迎观看图的演示系统!--------------------------\n\n");
	 printf("----------------------------1、创建图的邻接表-----------------------------\n");
	 printf("----------------------------2、广度优先遍历-------------------------------\n");
	 printf("----------------------------3、深度优先遍历-------------------------------\n");
	 printf("----------------------------4、最小生成树---------------------------------\n");
	 printf("----------------------------5、拓扑排序-----------------------------------\n");
	 printf("----------------------------6、最短路径-----------------------------------\n");
	 printf("----------------------------0、退出系统\n");
	 printf("请选择你的操作！       \n");
	 scanf("%d",&ch);
	 while(ch)
	 {
		 switch(ch)
		 {	
		 case 1:CreateAdjList(G);break;
		 case 2:printf("广度遍历结果\n");BFSTra(G);break;
		 case 3:printf("深度遍历结果\n");DFSTra(G);break;
		 case 4:Prim();break;
		 case 5:main0();break;
		 case 6:mainshort();break;
		 default:printf("选择错误！请重新输入！");
		 }
		 printf("\n\n\n					\n");	
	 printf("----------------------------欢迎观看图的演示系统!--------------------------\n\n");
	 printf("----------------------------1、创建图的邻接表-----------------------------\n");
	 printf("----------------------------2、广度优先遍历-------------------------------\n");
	 printf("----------------------------3、深度优先遍历-------------------------------\n");
	 printf("----------------------------4、最小生成树---------------------------------\n");
	 printf("----------------------------5、拓扑排序-----------------------------------\n");
	 printf("----------------------------6、最短路径-----------------------------------\n");
	 printf("----------------------------0、退出系统\n");
	 printf("请选择你的操作！   \n");
	 scanf("%d",&ch);
	 }
 }


void main()
{
	char choice;
	printf("------------------------------数据结构演示系统二-------------------------------\n");
	printf("------------------------------1.树的操作---------------------------------------\n");
	printf("------------------------------2.图的操作---------------------------------------\n");
	printf("------------------------------0.退出演示系统-----------------------------------\n");
	printf("\n请输入你的选择:  ");
	cin>>choice;
	while(choice!='0')
	{
		switch(choice)
		{
		case '1':main1();break;
		case '2':main2();break;
		default :printf("请输入1,2或者0.");
		}
			  printf("		\n\n\n			\n");
		      printf("------------------------------数据结构演示系统二-------------------------------\n");
		      printf("------------------------------1.树的操作---------------------------------------\n");
	          printf("------------------------------2.图的操作---------------------------------------\n");
	          printf("------------------------------0.退出演示系统-----------------------------------\n");
			  printf("\n 请输入你的选择:  ");
			  cin>>choice;
	}
}