tubianlideyanshi.cpp

图遍历的演示

#include <iostream>
using namespace std;
#define MAX_NAME 15 // 顶点值，字符串的最大长度+1
#define MAX_VERTEX_NUM 30
#define OVERFLOW -1
#define TRUE 1
#define MAX_INFO 80 // 相关信息字符串的最大长度+1
#define OK 1
#define FALSE 0
#define ERROR 0
enum VisitIf{unvisited,visited};//枚举 
typedef char InfoType;
typedef char VertexType[MAX_NAME]; // 字符串类型
struct EBox
{
   VisitIf mark; // 访问标记
   int ivex,jvex; // 该边依附的两个顶点的位置
   EBox *ilink,*jlink; // 分别指向依附这两个顶点的下一条边
   InfoType *info; // 该边信息指针
};
struct VexBox
{
   VertexType data;//字符串 
   EBox *firstedge; // 指向第一条依附该顶点的边
};
struct AMLGraph
{
   VexBox adjmulist[MAX_VERTEX_NUM];
   int vexnum,edgenum; // 无向图的当前顶点数和边数
};
int LocateVex(AMLGraph G,VertexType u)
{ // 初始条件: 无向图G存在,u和G中顶点有相同特征
   // 操作结果: 若G中存在顶点u,则返回该顶点在无向图中位置;否则返回-1
   int i;
   for(i=0;i<G.vexnum;++i)
     if(strcmp(u,G.adjmulist[i].data)==0)
       return i;
   return -1;
}
int CreateGraph(AMLGraph &G)
 { // 采用邻接多重表存储结构,构造无向图G
   int i,j,k,l,IncInfo;
   char s[MAX_INFO];
   VertexType va,vb;
   EBox *p;
   printf("请输入无向图G的顶点数,边数,边是否含其它信息(是:1，否:0): ");
   scanf("%d %d %d",&G.vexnum,&G.edgenum,&IncInfo);
   printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
   for(i=0;i<G.vexnum;++i) // 构造顶点向量
   {
     scanf("%s",G.adjmulist[i].data);
     G.adjmulist[i].firstedge=NULL;
   }
   printf("请顺序输入每条边的两个端点(以空格作为间隔):\n");
   for(k=0;k<G.edgenum;++k) // 构造表结点链表
   {
     scanf("%s%s%*c",va,vb); // %*c吃掉回车符
     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;
     if(IncInfo) // 边有相关信息
     {
       printf("请输入该弧的相关信息(<%d个字符)：",MAX_INFO);
       gets(s);
       l=strlen(s);
       if(l)
       {
         p->info=(char*)malloc((l+1)*sizeof(char));
         strcpy(p->info,s);
       }
     }
   }
   return OK;
 }

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); // 置边的访问标记为未被访问
   printf("%d个顶点：\n",G.vexnum);
   for(i=0;i<G.vexnum;++i)
     printf("%s ",G.adjmulist[i].data);
   printf("\n%d条边:\n",G.edgenum);
   for(i=0;i<G.vexnum;i++)
   {
     p=G.adjmulist[i].firstedge;
     while(p)
       if(p->ivex==i) // 边的i端与该顶点有关
       {
         if(!p->mark) // 只输出一次
         {
           printf("%s－%s ",G.adjmulist[i].data,G.adjmulist[p->jvex].data);
           p->mark=visited;
           if(p->info) // 输出附带信息
             printf("相关信息: %s ",p->info);
         }
         p=p->ilink;
       }
       else // 边的j端与该顶点有关
       {
         if(!p->mark) // 只输出一次
         {
           printf("%s－%s ",G.adjmulist[p->ivex].data,G.adjmulist[i].data);
           p->mark=visited;
           if(p->info) // 输出附带信息
             printf("相关信息: %s ",p->info);
         }
         p=p->jlink;
       }
     printf("\n");
   }
}
/**********************************深度优先**************************************/ 
bool visite[MAX_VERTEX_NUM]; // 访问标志数组(全局量)
int(*VisitFunc)(VertexType v);
int visit(VertexType v)
{
   printf("%s ",v);
   return OK;
}
void DFS(AMLGraph G,int v)
{
   int j;
   EBox *p;
   VisitFunc(G.adjmulist[v].data);
   visite[v]=TRUE;
   p=G.adjmulist[v].firstedge;
   while(p)
   {
     j=p->ivex==v?p->jvex:p->ivex;
     if(!visite[j])
       DFS(G,j);
     p=p->ivex==v?p->ilink:p->jlink;
   }
}
void DFSTraverse(AMLGraph G,int(*visit)(VertexType))
 { // 初始条件: 图G存在,Visit是顶点的应用函数。
   // 操作结果: 从第1个顶点起,深度优先遍历图G,并对每个顶点调用函数Visit
   //           一次且仅一次。一旦Visit()失败,则操作失败
   int v;
   VisitFunc=visit;
   for(v=0;v<G.vexnum;v++)
     visite[v]=FALSE;
   for(v=0;v<G.vexnum;v++)
     if(!visite[v])
       DFS(G,v);
   printf("\n");
}
/*************************************************************************************/
/*************************************广度优先********************************************/ 
typedef int QElemType; // 队列类型
typedef struct QNode
{
   QElemType data;
   QNode *next;
}*QueuePtr;
struct LinkQueue//队列 
{
   QueuePtr front,rear; // 队头、队尾指针
};
int InitQueue(LinkQueue &Q)
{ // 构造一个空队列Q
   if(!(Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))))
     exit(-1);
   Q.front->next=NULL;
   return OK;
}
int EnQueue(LinkQueue &Q,QElemType e)
{ // 插入元素e为Q的新的队尾元素
   QueuePtr p;
   if(!(p=(QueuePtr)malloc(sizeof(QNode)))) // 存储分配失败
     exit(OVERFLOW);
   p->data=e;
   p->next=NULL;
   Q.rear->next=p;
   Q.rear=p;
   return OK;
}
int QueueEmpty(LinkQueue Q)
{ // 若Q为空队列,则返回TRUE,否则返回FALSE
   if(Q.front==Q.rear)
     return TRUE;
   else
     return FALSE;
}
int 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;
}
VertexType& GetVex(AMLGraph G,int v)
{ // 初始条件: 无向图G存在,v是G中某个顶点的序号。操作结果: 返回v的值
   if(v>=G.vexnum||v<0)
     exit(0);
   return G.adjmulist[v].data;
}
int FirstAdjVex(AMLGraph G,VertexType v)
{ // 初始条件: 无向图G存在,v是G中某个顶点
   // 操作结果: 返回v的第一个邻接顶点的序号。若顶点在G中没有邻接顶点,则返回-1
   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;
}
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;
}
void BFSTraverse(AMLGraph G,int(*Visit)(VertexType))
{ // 初始条件: 图G存在,Visit是顶点的应用函数。
   // 操作结果: 从第1个顶点起,按广度优先非递归遍历图G,并对每个顶点调用函数
   //           Visit一次且仅一次。一旦Visit()失败,则操作失败。
   //           使用辅助队列Q和访问标志数组visite
   int v,u,w;
   VertexType w1,u1;
   LinkQueue Q;
   for(v=0;v<G.vexnum;v++)
     visite[v]=FALSE; // 置初值
   InitQueue(Q); // 置空的辅助队列Q
   for(v=0;v<G.vexnum;v++)
     if(!visite[v]) // v尚未访问
     {
       visite[v]=TRUE; // 设置访问标志为TRUE(已访问)
       Visit(G.adjmulist[v].data);
       EnQueue(Q,v); // v入队列
       while(!QueueEmpty(Q)) // 队列不空
       {
         DeQueue(Q,u); // 队头元素出队并置为u
         strcpy(u1,GetVex(G,u));
         for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,GetVex(G,w))))
           if(!visite[w]) // w为u的尚未访问的邻接顶点的序号
           {
             visite[w]=TRUE;
             Visit(G.adjmulist[w].data);
             EnQueue(Q,w);
           }
       }
     }
   printf("\n");
}
 /******************************************************************************************/
int main()
{
   int k,n;
   AMLGraph g;
   VertexType v1,v2;
   CreateGraph(g);
   Display(g);
   
   printf("深度优先搜索的结果:\n");
   DFSTraverse(g,visit);
   cout<<endl<<endl;
   
   printf("广度优先搜索的结果:\n");
   BFSTraverse(g,visit);
   
   system("pause");
   return 0;
}