gtraverse.cpp

关于图遍历的演示包括所有的源代码和执行文件

/*图遍历的演示-胡海洪*/
#include<iostream.h>
#include<malloc.h>
#include<conio.h>
#include<string.h>
#include<stdlib.h>
#include<fstream.h>

#define MAX_INFO 10          /* 相关信息字符串的最大长度+1 */
#define MAX_VERTEX_NUM 26    /* 图中顶点数的最大值*/
#define STACK_INIT_SIZE 100  /* 存储空间初始分量*/ 
#define STACKINCREMENT 10    /* 存储空间分配增量*/
#define OK 1
#define TRUE 1
#define ERROR 0
#define FALSE 0

typedef int SElemType;
typedef int QElemType;
typedef int Status;
typedef char VertexType;
typedef char InfoType;             /*相关信息类型*/

int Visited[MAX_VERTEX_NUM];  /*访问标志数组(全局量) */
VertexType Edge[2*MAX_VERTEX_NUM];
int (*VisitFunc)(VertexType v);
VertexType Path[MAX_VERTEX_NUM];
int IncInfo;


/* 单链队列－－队列的链式存储结构 */
typedef struct QNode{
 QElemType    data;
 struct QNode *next;
}QNode,*QueuePtr;

typedef struct{
 QueuePtr front;
 QueuePtr rear; /* 队头、队尾指针 */
}LinkQueue;

/*无向图的邻接多重表存储结构*/
typedef enum{unvisited,visited}VisitIf;
typedef struct EBox{
 VisitIf      mark;           /* 访问标记 */
 int          ivex,jvex;      /* 该边依附的两个顶点的位置 */
 struct EBox  *ilink,*jlink;  /* 分别指向依附这两个顶点的下一条边 */
 InfoType     *info;          /* 该边信息指针 */
}EBox;

typedef struct{
 VertexType data;
 EBox       *firstedge;       /* 指向第一条依附该顶点的边 */
}VexBox;

typedef struct{
 VexBox adjmulist[MAX_VERTEX_NUM];
 int    vexnum,edgenum;            /* 无向图的当前顶点数和边数 */
}AMLGraph;

/*树的二叉链表(孩子-兄弟)存储表示*/
typedef struct CSNode{
 VertexType     data;
 struct CSNode  *firstchild,*nextsibling;
}CSNode,*CSTree;

/*栈的顺序存储表示*/
typedef struct{
 SElemType  *base;
 SElemType  *top;      /*栈顶指针*/
 int        stacksize;
}SqStack;

 /*栈的基本操作*/
Status InitStack(SqStack &S)	
{  
 S.base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
 if(!S.base)
   exit(0);
 S.top=S.base;
 S.stacksize=STACK_INIT_SIZE;
 return OK;
} 

Status DestroyStack(SqStack &S)
{ /* 销毁栈S，S不再存在 */
 free(S.base);
 S.base=NULL;
 S.top=NULL;
 S.stacksize=0;
 return OK;
}

Status Push(SqStack &S,SElemType e)
{ /*入栈*/
 if(S.top-S.base>=S.stacksize)
   {
    S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
    if(!S.base)
      exit(0);
    S.top=S.base+S.stacksize;
    S.stacksize+=STACKINCREMENT;
   }
 *S.top++=e;
 return OK;
}

Status Pop(SqStack &S,SElemType &e)
{ /*出栈*/
 if(S.top==S.base)
   return ERROR;
 e=*--S.top;
 return OK;
}

Status StackEmpty(SqStack S)
{ /*判断栈是否为空*/
 if(S.top==S.base)
   return OK;
 else
   return ERROR;
}

 /* 链队列的基本操作 */
Status InitQueue(LinkQueue &Q)
{ /* 构造一个空队列Q */
 Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));
 if(!Q.front)
   exit(0);
 Q.front->next=NULL;
 return OK;
}

Status DestroyQueue(LinkQueue &Q)
{ /* 销毁队列Q(无论空否均可) */
 while(Q.front)
   {
    Q.rear=Q.front->next;
    free(Q.front);
    Q.front=Q.rear;
   }
 return OK;
}

Status QueueEmpty(LinkQueue Q)
{ /* 若Q为空队列,则返回TRUE,否则返回FALSE */
 if(Q.front==Q.rear)
   return OK;
 else
   return ERROR;
}

Status EnQueue(LinkQueue &Q,QElemType e)
{ /* 插入元素e为Q的新的队尾元素 */
 QueuePtr p=(QueuePtr)malloc(sizeof(QNode));
 if(!p) /* 存储分配失败 */
   exit(0);
 p->data=e;
 p->next=NULL;
 Q.rear->next=p;
 Q.rear=p;
 return OK;
}

Status DeQueue(LinkQueue &Q,QElemType &e)
{ /* 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR */
 QueuePtr p;
 if(Q.front==Q.rear)
   return ERROR;
 p=Q.front->next;
 e=p->data;
 Q.front->next=p->next;
 if(Q.rear==p)
   Q.rear=Q.front;
 free(p);
 return OK;
}

/*寻找顶点在图中的位置*/
int LocateVex(AMLGraph G,VertexType u)
{
 int i;
 for(i=0;i<G.vexnum;++i)
   if(u==G.adjmulist[i].data)
     return i;
 return -1;
}

/*返回v的顶点值*/
VertexType& GetVex(AMLGraph G,int v)
{
 if(v>=G.vexnum||v<0)
   exit(0);
 return G.adjmulist[v].data;
}

/*寻找v的第一个邻接顶点*/
int FirstAdjVex(AMLGraph G,VertexType v)
{
 int i;
 i=LocateVex(G,v);
 if(i<0)
   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;
}

/*返回v的(相对于w的)下一个邻接顶点*/
int NextAdjVex(AMLGraph G,VertexType v,VertexType w)
{
 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;
}

Status DeleteArc(AMLGraph &G,VertexType v,VertexType w)
{/* 在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 ERROR;  /* 图中没有该点或弧 */
   /* 以下使指向待删除边的第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 ERROR;
      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;
    if(p->info) /* 有相关信息 */
       free(p->info);
    free(p);
   }
 else
   if(p->ivex==i) /* 第1条边即为待删除边(情况2) */
     {
      G.adjmulist[j].firstedge=p->jlink;
      if(p->info) /* 有相关信息 */
        free(p->info);
      free(p);
     }
   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;
        if(p->info) /* 有相关信息 */
          free(p->info);
        free(p);
       }
     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--;
 return OK;
}

Status DeleteVex(AMLGraph &G,VertexType v)
{ /* 删除G中顶点v及其相关的边 */
 int i,j;
 VertexType w;
 EBox *p;
 i=LocateVex(G,v); /* i为待删除顶点的序号 */
 if(i<0)
   return ERROR;
 for(j=0;j<G.vexnum;j++) /* 删除与顶点v相连的边(如果有的话) */
   {
    if(j==i)
      continue;
    w=GetVex(G,j); /* w是第j个顶点的值 */
    DeleteArc(G,v,w);
   }
 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++) /* 修改顶点的序号 */
   {
    p=G.adjmulist[j].firstedge;
    if(p)
      {
       if(p->ivex==j+1)
         {
          p->ivex--;
          p=p->ilink;
         }
       else
         {
          p->jvex--;
          p=p->jlink;
         }
      }
   }
 return OK;
}

void DestroyGraph(AMLGraph &G)
{/*销毁一个图*/
 int i;
 for(i=G.vexnum-1;i>=0;i--)
   DeleteVex(G,G.adjmulist[i].data);
}

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 CreateGraph(AMLGraph &G)
{ /* 采用邻接多重表存储结构,构造无向图G */
 int i,j,k,l,cur=0;
 VertexType s[MAX_INFO];
 VertexType va,vb;
 EBox *p;
 cout<<endl<<"Please input the number of G.vexnum (EG. G.vexnum=10): ";
 cin>>G.vexnum;
 cout<<"Please input the number of G.edgenum (EG. G.edgenum=4): ";
 cin>>G.edgenum;
 cout<<"Please input the number of IncInfo (0 for none): ";
 cin>>IncInfo;
 cout<<"Please intput "<<G.vexnum<<" values of Vexs:"<<endl;
 for(i=0;i<G.vexnum;++i) /* 构造顶点向量 */
    cin>>G.adjmulist[i].data;
 cout<<"Please input the Edges orderly(interval by space):"<<endl;
 for(k=0;k<G.edgenum;++k) /* 构造表结点链表 */
   {
    cin>>va>>vb; /* 读入两个顶点*/
    Edge[cur++]=va;
    Edge[cur++]=vb;
    i=LocateVex(G,va); /* 一端 */
    j=LocateVex(G,vb); /* 另一端 */
    p=(EBox*)malloc(sizeof(EBox));
    p->mark=unvisited; /* 设初值 */
    p->ivex=i;
    p->jvex=j;
    p->info=NULL;
    p->ilink=G.adjmulist[i].firstedge; /* 插在表头 */
    G.adjmulist[i].firstedge=p;
    p->jlink=G.adjmulist[j].firstedge; /* 插在表头 */
    G.adjmulist[j].firstedge=p;    /*插入j链表尾部*/
    if(IncInfo)
      {
       cout<<"Please input Info: ";
       cin>>s;
       l=strlen(s);
       if(l)
         {
          p->info=(char*)malloc((l+1)*sizeof(char));
          p->info=s;
         }
      }
   }
}

void DFSTraverse(AMLGraph G,VertexType start,int(*visit)(VertexType))
{/*从start顶点起,深度优先遍历图G(非递归算法)*/
 int v,w,u;
 SqStack S,S2;
 InitStack(S);
 InitStack(S2);
 w=LocateVex(G,start);
 for(v=0;v<G.vexnum;v++)
   Visited[v]=0;
 for(v=0;v<G.vexnum;v++)
   if(!Visited[(v+w)%G.vexnum])
     {
      Push(S,(v+w)%G.vexnum);
      while(!StackEmpty(S))
        {
         Pop(S,u);
         if(!Visited[u])
           {
            Visited[u]=1;	
            visit(G.adjmulist[u].data);