tu.cpp

图的算法程序.最小生成树,最短路径等问题

 #include"stdio.h"
#define MAX 10
#define INF 65535
typedef enum{DGN,UDGN} graphkind;
typedef char vertextype;
typedef int adjtype;
struct
{
   vertextype vex;
   adjtype lowcost;
}closeedge[MAX];


typedef struct
{
     vertextype vexs[MAX+1];
     adjtype edges[MAX+1][MAX+1];
     int n,e;
}mgraph;


void creategn(mgraph*g,graphkind gk)
{

   int i,j,k;
   adjtype w;
   printf("\n\t\t 请输入图的顶点数和边数（格式为：顶点数，变数))\n\t\t");
   scanf("%d,%d",&(g->n),&(g->e));
   getchar();

   for(i=1;i<=g->n;i++)
	for(j=1;j<=g->n;j++)
	     g->edges[i][j]=INF;

   printf("\n\t\t 请输入各顶点的值：\n\t\t");
   for(i=1;i<=g->n;i++)
   {
       scanf("%c",&(g->vexs[i]));
       getchar();
       printf("\t\t");
   }
   printf("请输入边信息，如果不是网，请用0或者1表示边（弧）的存在与否。\n");
   printf("\t\t 如果是网，则输入权值！\n");
   printf("\t\t 输入格式为：端点1的序号，端点2的序号，1或者权值\n\t\t");
   for(k=1;k<=g->e;k++)
   {
      scanf("%d,%d,%d",&i,&j,&w);
      getchar();
      printf("\t\t");
      g->edges[i][j]=w;
	  if(gk==2)
	       g->edges[i][j]=w;
   }
   printf("\n\t\t 输入的各个顶点为:");
   for(i=1;i<=g->n;i++)
       printf("%c\t",g->vexs[i]);
       printf("\n\t\t 输入的邻接矩阵为:\n");
       for(i=1;i<=g->n;i++)
       {
	  printf("\n\t\t");
	  for(j=1;j<=g->n;j++)
		 printf("%d\t",g->edges[i][j]);
       }
   }
  
  
void prim(mgraph*g,int i)
 {
    int mincost;
    int j,k,m;
    int vexnum;
    vexnum=g->n;
    
    for(j=1;j<=g->n;j++)
            if(j!=1)
            {
                 closeedge[j].vex=g->vexs[i];
                 closeedge[j].lowcost=g->edges[i][j];
             }

	  closeedge[i].lowcost=0;
	  vexnum--;
	  while(vexnum!=0)
	  {
		  mincost=INF;
		  k=1;m=1;
		  while(k<=g->n)
		  {
			  if(closeedge[k].lowcost<mincost&&closeedge[k].lowcost!=0)
			  {
				  mincost=closeedge[k].lowcost;
				  m=k;
			  }
			  k++;
		  }
         printf("\t\t当前最小边的端点的值为：%c------%c\n",g->vexs[m],closeedge[m].vex);
         closeedge[m].lowcost=0;
         vexnum--;
         for(j=1;j<=g->n;j++)
                  if(g->edges[m][j]<closeedge[j].lowcost)
                    {
                        closeedge[j].vex=g->vexs[m];
                        closeedge[j].lowcost=g->edges[m][j];
                                           }
                     }
           }

void shortestpath_dij(mgraph*g, int i ,int *p, adjtype *d)
{
   int j,k,q,min,m,pre;
   int final[MAX];
   for(j=1;j<=g->n;j++)
{
   d[j]=g->edges[i][j];
   final[j]=0;
   if(d[j]<INF)
       p[j]=i;
   else p[j]=0;
}

d[i]=0; final[i]=1;
for(j=1;j<=g->n;j++)
{
    min=INF;
    for(k=1;k<=g->n;k++)
       if(!final[k]&&d[k]<min)
           {min=d[k];m=k;}
   final[m]=1;
for(k=1;k<=g->n;k++)
    if((!final[k])&&((min+g->edges[m][k])<d[k]))
        {
               d[k]=min+g->edges[m][k];
               p[k]=m;
        }
}
printf("\n\t\t");
for(j=1;j<=g->n;j++)
 {
    printf("%d\t%d",d[j],j);
      pre=p[j];
     while(pre!=0)
     { 
          printf("<---%d",pre);
             pre=p[pre];
     }
       printf("\n\t\t");
     }
}


main()
{
	    mgraph g;
		graphkind gk;
		vertextype a;
		char choice;
		int i,j=1,ch2,k;
		int visited[MAX];
		int p[MAX];
		adjtype d[MAX];
		while(j)
		{
			printf("\n");
			printf("\n");
			printf("\n");
			printf("\n");
			printf("\n\n\t图的数组表示\n");
			printf("\n\t\t***************************************************");
			printf("\n\t\t*          1----构造一个图                        *");
			printf("\n\t\t*          2----prim算法                          *");
			printf("\n\t\t*          3----最短路径算法                      *");
			printf("\n\t\t*          4----退出                              *");
			printf("\n\t\t***************************************************");
			printf("\n\t\t请输入要进行的操作：1到4。。。");
			scanf("%c",&choice);
			getchar();
			if(choice=='1')
			{
				printf("\t\t请输入图的类型（有向还是无向）\n");
				printf("\t\t如果是有向图或者有向网输入1，否则输入2\n\t\t");
				scanf("%d",&gk);getchar();
				creategn(&g,gk);
			}
			else if(choice=='2')
			{
				printf("\n\t\t请输入出发顶点的编号:");
				scanf("%d",&i);getchar();
				prim(&g,i);
			}
			else if(choice=='3')
			{
				printf("\n\t\t请输入出发顶点的编号:");
				scanf("%d",&i);getchar();
				shortestpath_dij(&g,i,p,d);

			}
			else if(choice='0')
			{
				j=4;
				printf("\t\t程序结束!\n");
			}
			else printf("\n\t\t输入错误！请重新输入！\n");
		}
}