adjmulist.cpp

用标准C++完成对图的深/广度优先搜索,使用邻接多重表的存储结构

#include <iostream>
#include <fstream>
#include <new>
#include <string>
#include <cassert>
#include "Adjmulist.h"
#include "Queue.h"
using namespace std;

 int LocateVex(AMLGraph& G,VertexType u)
 { /* 初始条件：无向图G存在，u和G中顶点有相同特征 */
   /* 操作结果：若G中存在顶点u，则返回该顶点在无向图中位置；否则返回-1 */
   int i;
   for(i=0;i<G.vexnum;++i)
     if(u == G.adjmulist[i].data)
       return i;
   return -1;
 }

 void CreateGraph(AMLGraph &G)
 { /* 采用邻接多重表存储结构，构造无向图G */
   int i,j,k;
   VertexType fileName;
   VertexType va,vb;
   EBox *p;
   ifstream infile;
   VertexType infileName;
   cout << "请输入数据文件名: " << endl;
   getline(cin,infileName);
   infile.open(infileName.data());
   assert(infile.is_open());
   infile >> G.vexnum;
   infile >> G.edgenum;
   for(i=0;i<G.vexnum;++i) /* 构造顶点向量 */
   {
     infile >> G.adjmulist[i].data;
     G.adjmulist[i].firstedge=NULL;
   }
   for(k=0;k<G.edgenum;++k) /* 构造表结点链表 */
   {
     infile >> va >> vb;
     i=LocateVex(G,va); /* 一端 */
     j=LocateVex(G,vb); /* 另一端 */
     p=new EBox;
     p->mark=unvisited; /* 设初值 */
     p->ivex=i;
     p->ilink=G.adjmulist[i].firstedge; /* 插在表头 */
     G.adjmulist[i].firstedge=p;
     p->jvex=j;
     p->jlink=G.adjmulist[j].firstedge; /* 插在表头 */
     G.adjmulist[j].firstedge=p;
    p->info=NULL;
   }
 }//CreateGraph

 VertexType& GetVex(AMLGraph G,int v)
 { /* 初始条件：无向图G存在，v是G中某个顶点的序号。操作结果：返回v的值 */
   if(v>=G.vexnum||v<0)
     exit(-1);
   return G.adjmulist[v].data;
 }

 int PutVex(AMLGraph &G,VertexType v,VertexType value)
 { /* 初始条件：无向图G存在，v是G中某个顶点。操作结果：对v赋新值value */
   int i;
   i=LocateVex(G,v);
   if(i<0) /* v不是G的顶点 */
     return -1;
   G.adjmulist[i].data = value;
   return 1;
 }

 int FirstAdjVex(AMLGraph& G,VertexType v)
 { /* 初始条件：无向图G存在，v是G中某个顶点 */
   /* 操作结果：返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点，则返回-1 */
   int i;
   i=LocateVex(G,v);
   if(i<0) /* G中不存在顶点v */
     return -1;
   if(G.adjmulist[i].firstedge) /* v有邻接顶点 */
     if(G.adjmulist[i].firstedge->ivex==i)
       return G.adjmulist[i].firstedge->jvex;
     else
       return G.adjmulist[i].firstedge->ivex;
   else
     return -1;
 }

 int NextAdjVex(AMLGraph& G,VertexType v,VertexType w)
 { /* 初始条件：无向图G存在，v是G中某个顶点，w是v的邻接顶点 */
   /* 操作结果：返回v的(相对于w的)下一个邻接顶点的序号。若w是v的最后一个邻接点，则返回-1 */
   int i,j;
   EBox *p;
   i=LocateVex(G,v); /* i是顶点v的序号 */
   j=LocateVex(G,w); /* j是顶点w的序号 */
   if(i<0||j<0) /* v或w不是G的顶点 */
     return -1;
   p=G.adjmulist[i].firstedge; /* p指向顶点v的第1条边 */
   while(p)
     if(p->ivex==i&&p->jvex!=j) /* 不是邻接顶点w(情况1) */
       p=p->ilink; /* 找下一个邻接顶点 */
     else if(p->jvex==i&&p->ivex!=j) /* 不是邻接顶点w(情况2) */
       p=p->jlink; /* 找下一个邻接顶点 */
     else /* 是邻接顶点w */
       break;
   if(p&&p->ivex==i&&p->jvex==j) /* 找到邻接顶点w(情况1) */
   {
     p=p->ilink;
     if(p&&p->ivex==i)
       return p->jvex;
     else if(p&&p->jvex==i)
       return p->ivex;
   }
   if(p&&p->ivex==j&&p->jvex==i) /* 找到邻接顶点w(情况2) */
   {
     p=p->jlink;
     if(p&&p->ivex==i)
       return p->jvex;
     else if(p&&p->jvex==i)
       return p->ivex;
   }
   return -1;
 }

 int InsertVex(AMLGraph& G,VertexType v)
 { /* 初始条件：无向图G存在，v和G中顶点有相同特征 */
   /* 操作结果：在G中增添新顶点v(不增添与顶点相关的弧，留待InsertArc()去做) */
   if(G.vexnum==MAX_VERTEX_NUM) /* 结点已满，不能插入 */
     return -1;
   if(LocateVex(G,v) >= 0) /* 结点已存在，不能插入 */
     return -1;
   G.adjmulist[G.vexnum].data = v;
   G.adjmulist[G.vexnum++].firstedge=NULL;
   return 1;
 }

 int DeleteArc(AMLGraph& G,VertexType v,VertexType w)
 { /* 初始条件：无向图G存在，v和w是G中两个顶点。操作结果：在G中删除弧<v,w> */
   int i,j;
   EBox *p,*q;
   i=LocateVex(G,v);
   j=LocateVex(G,w);
   if(i<0||j<0||i==j)
     return -1;  /* 图中没有该点或弧。以下使指向待删除边的第1个指针绕过这条边 */
   p=G.adjmulist[i].firstedge; /* p指向顶点v的第1条边 */
   if(p&&p->jvex==j) /* 第1条边即为待删除边(情况1) */
     G.adjmulist[i].firstedge=p->ilink;
   else if(p&&p->ivex==j) /* 第1条边即为待删除边(情况2) */
     G.adjmulist[i].firstedge=p->jlink;
   else /* 第1条边不是待删除边 */
   {
     while(p) /* 向后查找弧<v,w> */
       if(p->ivex==i&&p->jvex!=j) /* 不是待删除边 */
       {
         q=p;
         p=p->ilink; /* 找下一个邻接顶点 */
       }
       else if(p->jvex==i&&p->ivex!=j) /* 不是待删除边 */
       {
         q=p;
         p=p->jlink; /* 找下一个邻接顶点 */
       }
       else /* 是邻接顶点w */
         break;
     if(!p) /* 没找到该边 */
       return -1;
     if(p->ivex==i&&p->jvex==j) /* 找到弧<v,w>(情况1) */
       if(q->ivex==i)
         q->ilink=p->ilink;
       else
         q->jlink=p->ilink;
     else if(p->ivex==j&&p->jvex==i) /* 找到弧<v,w>(情况2) */
       if(q->ivex==i)
         q->ilink=p->jlink;
       else
         q->jlink=p->jlink;
   } /* 以下由另一顶点起找待删除边且删除之 */
   p=G.adjmulist[j].firstedge; /* p指向顶点w的第1条边 */
   if(p->jvex==i) /* 第1条边即为待删除边(情况1) */
     G.adjmulist[j].firstedge=p->ilink;
   else if(p->ivex==i) /* 第1条边即为待删除边(情况2) */
     G.adjmulist[j].firstedge=p->jlink;
   else /* 第1条边不是待删除边 */
   {
     while(p) /* 向后查找弧<v,w> */
       if(p->ivex==j&&p->jvex!=i) /* 不是待删除边 */
       {
         q=p;
         p=p->ilink; /* 找下一个邻接顶点 */
       }
       else if(p->jvex==j&&p->ivex!=i) /* 不是待删除边 */
       {
         q=p;
         p=p->jlink; /* 找下一个邻接顶点 */
       }
       else /* 是邻接顶点v */
         break;
     if(p->ivex==i&&p->jvex==j) /* 找到弧<v,w>(情况1) */
       if(q->ivex==j)
         q->ilink=p->jlink;
       else
         q->jlink=p->jlink;
     else if(p->ivex==j&&p->jvex==i) /* 找到弧<v,w>(情况2) */
       if(q->ivex==j)
         q->ilink=p->ilink;
       else
         q->jlink=p->ilink;
   }
   if(p->info) /* 有相关信息(或权值) */
     free(p->info); /* 释放相关信息(或权值) */
   free(p); /* 释放结点 */
   G.edgenum--; /* 边数-1 */
   return 1;
 }

 int DeleteVex(AMLGraph& G,VertexType v)
 { /* 初始条件：无向图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的边 */
   int i,j;
   EBox *p;
   i=LocateVex(G,v); /* i为待删除顶点的序号 */
   if(i<0)
     return -1;
   for(j=0;j<G.vexnum;j++) /* 删除与顶点v相连的边(如果有的话) */
     DeleteArc(G,v,G.adjmulist[j].data); /* 如果存在此弧，则删除 */
   for(j=i+1;j<G.vexnum;j++) /* 排在顶点v后面的顶点的序号减1 */
     G.adjmulist[j-1] = G.adjmulist[j];
   G.vexnum--; /* 顶点数减1 */
   for(j=i;j<G.vexnum;j++) /* 修改序号大于i的顶点在表结点中的序号 */
   {
     p=G.adjmulist[j].firstedge;
     if(p)
       if(p->ivex==j+1)
       {
         p->ivex--;
         p=p->ilink;
       }
       else
       {
         p->jvex--;
         p=p->jlink;
       }
   }
   return 1;
 }

 void DestroyGraph(AMLGraph& G)
 { /* 初始条件：有向图G存在。操作结果：销毁有向图G */
   int i;
   for(i=G.vexnum-1;i >= 0;i--) /* 由大到小依次删除顶点 */
     DeleteVex(G,G.adjmulist[i].data);
 }

 int InsertArc(AMLGraph& G,VertexType v,VertexType w)
 { /* 初始条件：无向图G存在，v和W是G中两个顶点。操作结果：在G中增添弧<v,w> */
   int i,j;
   EBox *p;
   i=LocateVex(G,v); /* 一端 */
   j=LocateVex(G,w); /* 另一端 */
   if(i<0||j<0||i==j)
     return -1;
   p=new EBox;
   p->mark=unvisited;
   p->ivex=i;
   p->ilink=G.adjmulist[i].firstedge; /* 插在表头 */
   G.adjmulist[i].firstedge=p;
   p->jvex=j;
   p->jlink=G.adjmulist[j].firstedge; /* 插在表头 */
   G.adjmulist[j].firstedge=p;
   p->info=NULL;
   G.edgenum++;
   return 1;
 }

 bool Visited[MAX_VERTEX_NUM]; /* 访问标志数组(全局量) */
 void(*VisitFunc)(VertexType v);
 void DFS(AMLGraph& G,int v)
 {
   int j;
   EBox *p;
   VisitFunc(G.adjmulist[v].data);
   Visited[v]=true;
   p=G.adjmulist[v].firstedge;
   while(p)
   {
     j=p->ivex==v?p->jvex:p->ivex;
     if(!Visited[j])
       DFS(G,j);
     p=p->ivex==v?p->ilink:p->jlink;
   }
 }

 void DFSTraverse(AMLGraph& G,void(*visit)(VertexType))
 { /* 初始条件：图G存在，Visit是顶点的应用函数。算法7.4 */
   /* 操作结果：从第1个顶点起，深度优先遍历图G，并对每个顶点调用函数Visit一次且仅一次 */
   int v;
   VisitFunc=visit;
   for(v=0;v<G.vexnum;v++)
     Visited[v]=false;
   for(v=0;v<G.vexnum;v++)
     if(!Visited[v])
       DFS(G,v);
   printf("\n");
 }

 void BFSTraverse(AMLGraph& G,void(*Visit)(VertexType))
 { /* 初始条件：图G存在，Visit是顶点的应用函数。算法7.6 */
   /* 操作结果：从第1个顶点起，按广度优先非递归遍历图G，并对每个顶点调用函数 */
   /*           Visit一次且仅一次。使用辅助队列Q和访问标志数组visited */
   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++)
     if(!Visited[v]) /* v尚未访问 */
     {
       Visited[v]=true; /* 设置访问标志为true(已访问) */
       Visit(G.adjmulist[v].data);
       EnQueue(Q,v); /* v入队列 */
       while(!QueueEmpty(Q)) /* 队列不空 */
       {
         DeQueue(Q,u); /* 队头元素出队并置为u */
         for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
           if(!Visited[w]) /* w为u的尚未访问的邻接顶点的序号 */
           {
             Visited[w]=true;
             Visit(G.adjmulist[w].data);
             EnQueue(Q,w);
           }
       }
     }
   cout << endl;
 }

 void MarkUnvizited(AMLGraph& G)
 { /* 置边的访问标记为未被访问 */
   int i;
   EBox *p;
   for(i=0;i<G.vexnum;i++)
   {
     p=G.adjmulist[i].firstedge;
     while(p)
     {
       p->mark=unvisited;
       if(p->ivex==i)
         p=p->ilink;
       else
         p=p->jlink;
     }
   }
 }

 void Display(AMLGraph& G)
 { /* 输出无向图的邻接多重表G */
   int i;
   EBox *p;
   MarkUnvizited(G); /* 置边的访问标记为未被访问 */
   cout << G.vexnum << "个顶点：" << endl;
   for(i=0;i<G.vexnum;++i)
     cout << G.adjmulist[i].data;
   cout << endl << G.edgenum << "条边:" << endl;
   for(i=0;i<G.vexnum;i++)
   {
     p=G.adjmulist[i].firstedge;
     while(p)
       if(p->ivex==i) /* 边的i端与该顶点有关 */
       {
         if(!p->mark) /* 只输出一次 */
         {
           cout << G.adjmulist[i].data << "--" << G.adjmulist[p->jvex].data;
           p->mark=visited;
        }
         p=p->ilink;
       }
       else /* 边的j端与该顶点有关 */
       {
         if(!p->mark) /* 只输出一次 */
         {
           cout << G.adjmulist[p->ivex].data << "--" << G.adjmulist[i].data;
           p->mark=visited;
         }
         p=p->jlink;
       }
     cout << endl;
   }
 }