bo7-1.cpp

数据结构中关于图的存储、遍历以及其他重要操作的实现

 // bo7-1.cpp 图的数组(邻接矩阵)存储(存储结构由c7-1.h定义)的基本操作(21个)，包括算法7.1、
 // 7.2、算法7.4～7.6
 int LocateVex(MGraph G,VertexType u)
 { // 初始条件：图G存在，u和G中顶点有相同特征
   // 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回-1
   int i;
   for(i=0;i<G.vexnum;++i)
     if(strcmp(u,G.vexs[i])==0)
       return i;
   return -1;
 }

 void CreateFUDG(MGraph &G)
 { // 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向图G
   int i,j,k;
   char filename[13];
   VertexType va,vb;
   FILE *graphlist;
   printf("请输入数据文件名(f7-1.txt或f7-2.txt)：");
   scanf("%s",filename);
   graphlist=fopen(filename,"r"); // 打开数据文件，并以graphlist表示
   fscanf(graphlist,"%d",&G.vexnum);
   fscanf(graphlist,"%d",&G.arcnum);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     fscanf(graphlist,"%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=0; // 图
       G.arcs[i][j].info=NULL; // 没有相关信息
     }
   for(k=0;k<G.arcnum;++k)
   {
     fscanf(graphlist,"%s%s",va,vb);
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=G.arcs[j][i].adj=1; // 无向图
   }
   fclose(graphlist); // 关闭数据文件
   G.kind=UDG;
 }

 void CreateFUDN(MGraph &G)
 { // 采用数组(邻接矩阵)表示法，由文件构造没有相关信息的无向网G
   int i,j,k,w;
   char filename[13];
   VertexType va,vb;
   FILE *graphlist;
   printf("请输入数据文件名：");
   scanf("%s",filename);
   graphlist=fopen(filename,"r"); // 打开数据文件，并以graphlist表示
   fscanf(graphlist,"%d",&G.vexnum);
   fscanf(graphlist,"%d",&G.arcnum);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     fscanf(graphlist,"%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=INFINITY; // 网
       G.arcs[i][j].info=NULL; // 没有相关信息
     }
   for(k=0;k<G.arcnum;++k)
   {
     fscanf(graphlist,"%s%s%d",va,vb,&w);
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=G.arcs[j][i].adj=w; // 无向网
   }
   fclose(graphlist); // 关闭数据文件
   G.kind=UDN;
 }

 void CreateDG(MGraph &G)
 { // 采用数组(邻接矩阵)表示法，构造有向图G
   int i,j,k,l,IncInfo;
   char s[MAX_INFO];
   VertexType va,vb;
   printf("请输入有向图G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=0; // 图
       G.arcs[i][j].info=NULL;
     }
   printf("请输入%d条弧的弧尾 弧头(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%*c",va,vb);  // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=1; // 有向图
     if(IncInfo)
     {
       printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       l=strlen(s);
       if(l)
       {
         G.arcs[i][j].info=(char*)malloc((l+1)*sizeof(char)); // 有向
         strcpy(G.arcs[i][j].info,s);
       }
     }
   }
   G.kind=DG;
 }

 void CreateDN(MGraph &G)
 { // 采用数组(邻接矩阵)表示法，构造有向网G
   int i,j,k,w,IncInfo;
   char s[MAX_INFO];
   VertexType va,vb;
   printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=INFINITY; // 网
       G.arcs[i][j].info=NULL;
     }
   printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%d%*c",va,vb,&w);  // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=w; // 有向网
     if(IncInfo)
     {
       printf("请输入该弧的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       w=strlen(s);
       if(w)
       {
         G.arcs[i][j].info=(char*)malloc((w+1)*sizeof(char)); // 有向
         strcpy(G.arcs[i][j].info,s);
       }
     }
   }
   G.kind=DN;
 }

 void CreateUDG(MGraph &G)
 { // 采用数组(邻接矩阵)表示法，构造无向图G
   int i,j,k,l,IncInfo;
   char s[MAX_INFO];
   VertexType va,vb;
   printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=0; // 图
       G.arcs[i][j].info=NULL;
     }
   printf("请输入%d条边的顶点1 顶点2(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%*c",va,vb); // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=G.arcs[j][i].adj=1; // 无向图
     if(IncInfo)
     {
       printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       l=strlen(s);
       if(l)
       {
         G.arcs[i][j].info=G.arcs[j][i].info=(char*)malloc((l+1)*sizeof(char));
	 // 无向，两个指针指向同一个信息
	 strcpy(G.arcs[i][j].info,s);
       }
     }
   }
   G.kind=UDG;
 }

 void CreateUDN(MGraph &G)
 { // 采用数组(邻接矩阵)表示法，构造无向网G。算法7.2
   int i,j,k,w,IncInfo;
   char s[MAX_INFO];
   VertexType va,vb;
   printf("请输入无向网G的顶点数,边数,边是否含其它信息(是:1,否:0): ");
   scanf("%d,%d,%d",&G.vexnum,&G.arcnum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
     scanf("%s",G.vexs[i]);
   for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵
     for(j=0;j<G.vexnum;++j)
     {
       G.arcs[i][j].adj=INFINITY; // 网
       G.arcs[i][j].info=NULL;
     }
   printf("请输入%d条边的顶点1 顶点2 权值(以空格作为间隔): \n",G.arcnum);
   for(k=0;k<G.arcnum;++k)
   {
     scanf("%s%s%d%*c",va,vb,&w); // %*c吃掉回车符
     i=LocateVex(G,va);
     j=LocateVex(G,vb);
     G.arcs[i][j].adj=G.arcs[j][i].adj=w; // 无向
     if(IncInfo)
     {
       printf("请输入该边的相关信息(<%d个字符): ",MAX_INFO);
       gets(s);
       w=strlen(s);
       if(w)
       {
         G.arcs[i][j].info=G.arcs[j][i].info=(char*)malloc((w+1)*sizeof(char));
         // 无向，两个指针指向同一个信息
         strcpy(G.arcs[i][j].info,s);
       }
     }
   }
   G.kind=UDN;
 }

 void CreateGraph(MGraph &G)
 { // 采用数组(邻接矩阵)表示法，构造图G。算法7.1改
   printf("请输入图G的类型(有向图:0,有向网:1,无向图:2,无向网:3): ");
   scanf("%d",&G.kind);
   switch(G.kind)
   {
     case DG: CreateDG(G); // 构造有向图
              break;
     case DN: CreateDN(G); // 构造有向网
              break;
     case UDG:CreateUDG(G); // 构造无向图
              break;
     case UDN:CreateUDN(G); // 构造无向网
   }
 }

 void DestroyGraph(MGraph &G)
 { // 初始条件：图G存在。操作结果：销毁图G
   int i,j,k=0;
   if(G.kind%2) // 网
     k=INFINITY; // k为两顶点之间无边或弧时邻接矩阵元素的值
   for(i=0;i<G.vexnum;i++) // 释放弧或边的相关信息(如果有的话)
     if(G.kind<2) // 有向
     {
       for(j=0;j<G.vexnum;j++)
         if(G.arcs[i][j].adj!=k) // 有弧
           if(G.arcs[i][j].info) // 有相关信息
           {
             free(G.arcs[i][j].info);
             G.arcs[i][j].info=NULL;
           }
     } // 加括号为避免if-else对配错
     else // 无向
       for(j=i+1;j<G.vexnum;j++) // 只查上三角
         if(G.arcs[i][j].adj!=k) // 有边
           if(G.arcs[i][j].info) // 有相关信息