bo7-2.cpp

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

       {
         G.arcnum--; // 边或弧数-1
         if(G.kind==1) // 有向网
           free(p->data.info); // 释放动态生成的权值空间
       }
       free(p); // 释放v为入度的结点
     }
     for(k=j+1;k<=G.vexnum;k++) // 对于adjvex域>j的结点，其序号-1
     {
       e.adjvex=k;
       p=Point(G.vertices[i].firstarc,e,equalvex,p1); // Point()在func2-1.cpp中
       if(p)
         p->data.adjvex--; // 序号-1(因为前移)
     }
   }
   return OK;
 }

 Status InsertArc(ALGraph &G,VertexType v,VertexType w)
 { // 初始条件：图G存在，v和w是G中两个顶点
   // 操作结果：在G中增添弧<v,w>，若G是无向的，则还增添对称弧<w,v>
   ElemType e;
   int i,j;
   i=LocateVex(G,v); // 弧尾或边的序号
   j=LocateVex(G,w); // 弧头或边的序号
   if(i<0||j<0)
     return ERROR;
   G.arcnum++; // 图G的弧或边的数目加1
   e.adjvex=j;
   e.info=NULL; // 初值
   if(G.kind%2) // 网
   {
     e.info=(int *)malloc(sizeof(int)); // 动态生成存放权值的空间
     printf("请输入弧(边)%s→%s的权值: ",v,w);
     scanf("%d",e.info);
   }
   ListInsert(G.vertices[i].firstarc,1,e); // 将e插在弧尾的表头，在bo2-8.cpp中
   if(G.kind>=2) // 无向，生成另一个表结点
   {
     e.adjvex=i; // e.info不变
     ListInsert(G.vertices[j].firstarc,1,e); // 将e插在弧头的表头
   }
   return OK;
 }

 Status DeleteArc(ALGraph &G,VertexType v,VertexType w)
 { // 初始条件：图G存在，v和w是G中两个顶点
   // 操作结果：在G中删除弧<v,w>，若G是无向的，则还删除对称弧<w,v>
   int i,j;
   Status k;
   ElemType e;
   i=LocateVex(G,v); // i是顶点v(弧尾)的序号
   j=LocateVex(G,w); // j是顶点w(弧头)的序号
   if(i<0||j<0||i==j)
     return ERROR;
   e.adjvex=j;
   k=DeleteElem(G.vertices[i].firstarc,e,equalvex); // 在func2-1.cpp中
   if(k) // 删除成功
   {
     G.arcnum--; // 弧或边数减1
     if(G.kind%2) // 网
       free(e.info);
     if(G.kind>=2) // 无向，删除对称弧<w,v>
     {
       e.adjvex=i;
       DeleteElem(G.vertices[j].firstarc,e,equalvex);
     }
     return OK;
   }
   else // 没找到待删除的弧
     return ERROR;
 }

 Boolean visited[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
 void(*VisitFunc)(char* v); // 函数变量(全局量)
 void DFS(ALGraph G,int v)
 { // 从第v个顶点出发递归地深度优先遍历图G。算法7.5
   int w;
   visited[v]=TRUE; // 设置访问标志为TRUE(已访问)
   VisitFunc(G.vertices[v].data); // 访问第v个顶点
   for(w=FirstAdjVex(G,G.vertices[v].data);w>=0;w=NextAdjVex(G,G.vertices[v].data,G.vertices[w].data))
     if(!visited[w])
       DFS(G,w); // 对v的尚未访问的邻接点w递归调用DFS
 }

 void DFSTraverse(ALGraph G,void(*Visit)(char*))
 { // 对图G作深度优先遍历。算法7.4
   int v;
   VisitFunc=Visit; // 使用全局变量VisitFunc，使DFS不必设函数指针参数
   for(v=0;v<G.vexnum;v++)
     visited[v]=FALSE; // 访问标志数组初始化
   for(v=0;v<G.vexnum;v++)
     if(!visited[v])
       DFS(G,v); // 对尚未访问的顶点调用DFS
   printf("\n");
 }

 typedef int QElemType; // 队列元素类型
 #include"c3-2.h" // 链队列的存储结构
 #include"bo3-2.cpp" // 链队列的基本操作
 void BFSTraverse(ALGraph G,void(*Visit)(char*))
 {//按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。算法7.6
   int v,u,w;
   LinkQueue Q;
   for(v=0;v<G.vexnum;++v)
     visited[v]=FALSE; // 置初值
   InitQueue(Q); // 置空的辅助队列Q
   for(v=0;v<G.vexnum;v++) // 如果是连通图，只v=0就遍历全图
     if(!visited[v]) // v尚未访问
     {
       visited[v]=TRUE;
       Visit(G.vertices[v].data);
       EnQueue(Q,v); // v入队列
       while(!QueueEmpty(Q)) // 队列不空
       {
         DeQueue(Q,u); // 队头元素出队并置为u
         for(w=FirstAdjVex(G,G.vertices[u].data);w>=0;w=NextAdjVex(G,G.vertices[u].data,G.vertices[w].data))
           if(!visited[w]) // w为u的尚未访问的邻接顶点
           {
             visited[w]=TRUE;
             Visit(G.vertices[w].data);
             EnQueue(Q,w); // w入队
	   }
       }
     }
   printf("\n");
 }

 void DFS1(ALGraph G,int v,void(*Visit)(char*))
 { // 从第v个顶点出发递归地深度优先遍历图G。仅适用于邻接表存储结构
   ArcNode *p; // p指向表结点
   visited[v]=TRUE; // 设置访问标志为TRUE(已访问)
   Visit(G.vertices[v].data); // 访问该顶点
   for(p=G.vertices[v].firstarc;p;p=p->next) // p依次指向v的邻接顶点
     if(!visited[p->data.adjvex])
       DFS1(G,p->data.adjvex,Visit); // 对v的尚未访问的邻接点递归调用DFS1
 }

 void DFSTraverse1(ALGraph G,void(*Visit)(char*))
 { // 对图G作深度优先遍历。DFS1设函数指针参数
   int v;
   for(v=0;v<G.vexnum;v++)
     visited[v]=FALSE; // 访问标志数组初始化，置初值为未被访问
   for(v=0;v<G.vexnum;v++) // 如果是连通图，只v=0就遍历全图
     if(!visited[v]) // v尚未被访问
       DFS1(G,v,Visit); // 对v调用DFS1
   printf("\n");
 }

 void BFSTraverse1(ALGraph G,void(*Visit)(char*))
 { // 按广度优先非递归遍历图G。使用辅助队列Q和访问标志数组visited。仅适用于邻接表结构
   int v,u;
   ArcNode *p; // p指向表结点
   LinkQueue Q; // 链队列类型
   for(v=0;v<G.vexnum;++v)
     visited[v]=FALSE; // 置初值为未被访问
   InitQueue(Q); // 初始化辅助队列Q
   for(v=0;v<G.vexnum;v++) // 如果是连通图，只v=0就遍历全图
     if(!visited[v]) // v尚未被访问
     {
       visited[v]=TRUE; // 设v为已被访问
       Visit(G.vertices[v].data); // 访问v
       EnQueue(Q,v); // v入队列
       while(!QueueEmpty(Q)) // 队列不空
       {
         DeQueue(Q,u); // 队头元素出队并置为u
         for(p=G.vertices[u].firstarc;p;p=p->next) // p依次指向u的邻接顶点
           if(!visited[p->data.adjvex]) // u的邻接顶点尚未被访问
           {
             visited[p->data.adjvex]=TRUE; // 该邻接顶点设为已被访问
             Visit(G.vertices[p->data.adjvex].data); // 访问该邻接顶点
             EnQueue(Q,p->data.adjvex); // 入队该邻接顶点序号
           }
       }
     }
   printf("\n");
 }

 void Display(ALGraph G)
 { // 输出图的邻接矩阵G
   int i;
   ArcNode *p;
   switch(G.kind)
   {
     case DG: printf("有向图\n");
	      break;
     case DN: printf("有向网\n");
	      break;
     case UDG:printf("无向图\n");
	      break;
     case UDN:printf("无向网\n");
   }
   printf("%d个顶点：\n",G.vexnum);
   for(i=0;i<G.vexnum;++i)
     printf("%s ",G.vertices[i].data);
   printf("\n%d条弧(边):\n",G.arcnum);
   for(i=0;i<G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p)
     {
       if(G.kind<=1||i<p->data.adjvex) // 有向或无向两次中的一次
       {
         printf("%s→%s ",G.vertices[i].data,G.vertices[p->data.adjvex].data);
         if(G.kind%2) // 网
           printf(":%d ",*(p->data.info));
       }
       p=p->nextarc;
     }
     printf("\n");
   }
 }