gtraverse.cpp

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

            for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;
	        w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
	      if(!Visited[w])
	         Push(S2,w);
            while(!StackEmpty(S2))
              {
               Pop(S2,u);
               Push(S,u);
              }
           }
        }
     }
 DestroyStack(S);    /*销毁栈,释放其空间*/
 DestroyStack(S2);
}

void BFSTraverse(AMLGraph G,VertexType start,int(*Visit)(VertexType))
{ /*从start顶点起,广度优先遍历图G*/
 int v,u,w,z;
 LinkQueue Q;
 for(v=0;v<G.vexnum;v++)
   Visited[v]=0; /* 置初值 */
 InitQueue(Q);  
 z=LocateVex(G,start);
 for(v=0;v<G.vexnum;v++)
   if(!Visited[(v+z)%G.vexnum])       /* v尚未访问 */
     {
      Visited[(v+z)%G.vexnum]=1;     /* 设置访问标志为TRUE(已访问) */
      Visit(G.adjmulist[(v+z)%G.vexnum].data);
      EnQueue(Q,(v+z)%G.vexnum);
      while(!QueueEmpty(Q)) /* 队列不空 */
	{
	 DeQueue(Q,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]) 
	     {
	      Visited[w]=1;
	      Visit(G.adjmulist[w].data);
	      EnQueue(Q,w);
	     }
	}
   }
 DestroyQueue(Q); /*销毁队列,释放其占用空间*/
}

void PrintTraverse(CSTree T)
{ /*打印树的边*/
 CSTree p;
 for(p=T->firstchild;p;p=p->nextsibling)
   {
    cout<<ends<<T->data<<'-'<<p->data;
    PrintTraverse(p);  /*打印子树*/
   }
}

void PrintAllTraverse(CSTree T)
{  /*打印森林的边*/
 CSTree p;
 for(p=T;p;p=p->nextsibling)
   PrintTraverse(p);
}

void Display(AMLGraph G)
{ /* 输出无向图的邻接多重表G */
 int i;
 EBox *p;
 MarkUnvizited(G); 
 cout<<"This graph has "<<G.vexnum<<" Vexs:"<<endl;
 for(i=0;i<G.vexnum;++i)
   cout<<ends<<G.adjmulist[i].data;
 cout<<endl<<"This graph has "<<G.edgenum<<" Edges:"<<endl;
 for(i=0;i<G.vexnum;i++)
   {
    p=G.adjmulist[i].firstedge;
    while(p)
      if(p->ivex==i)   /* 边的i端与该顶点有关 */
	{
	 if(!p->mark)  /* 只输出一次 */
	   {
	    cout<<ends<<G.adjmulist[i].data<<'-'<<G.adjmulist[p->jvex].data;
	    p->mark=visited;
	    if(p->info)  /* 输出附带信息 */
	      cout<<"The Info:"<<p->info<<ends;
	   }
	 p=p->ilink;
	}
      else /* 边的j端与该顶点有关 */
	{
	 if(!p->mark) /* 只输出一次 */
	   {
	    cout<<ends<<G.adjmulist[p->ivex].data<<'-'<<G.adjmulist[i].data;
	    p->mark=visited;
	    if(p->info)  /* 输出附带信息 */
	      cout<<"The Info:"<<p->info<<ends;
	   }
	p=p->jlink;
       }
     cout<<endl;
    }
}

void DFSTree(AMLGraph G,int v,CSTree &DT)
{  /*从第v个顶点出发深度遍历图G,建立以DT为根的生成树*/
 int w,first=1;
 CSTree p,q;
 Visited[v]=1;
 for(w=FirstAdjVex(G,G.adjmulist[v].data);w>=0;w=NextAdjVex(G,G.adjmulist[v].data,
     G.adjmulist[w].data))
   if(!Visited[w])
     {
      p=(CSTree)malloc(sizeof(CSNode));     /*分配孩子结点*/
      p->data=G.adjmulist[w].data;
      p->firstchild=NULL;
      p->nextsibling=NULL;
      if(first)              /*w是v的第一个未被访问的邻接顶点是根的左孩子结点*/
	{
	 DT->firstchild=p;
	 first=0;
	}
      else              /*w是v的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/
	 q->nextsibling=p;
      q=p;
      DFSTree(G,w,q);  /*从第w个顶点出发深度优先遍历图G,建立子生成树q*/
     }
}

void DFSForest(AMLGraph G,VertexType start,CSTree &DT)
{ /*建立图G的深度优先生成森树的(最左)孩子(右)兄弟链表DT*/
 int v,w;
 CSTree p,q;
 DT=NULL;
 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])  /*start顶点为新的生成树的根结点*/
     {
      p=(CSTree)malloc(sizeof(CSNode));
      p->data=GetVex(G,(v+w)%G.vexnum);
      p->firstchild=NULL;
      p->nextsibling=NULL;
      if(!DT)               /*是第一棵生成树的根*/
        DT=p;
      else
	q->nextsibling=p;   /*是其他生成树的根(前一棵的根的"兄弟")*/
      q=p;                  /*q指示当前生成树的根*/
      DFSTree(G,(v+w)%G.vexnum,p);    /*建立以p为根的生成树*/
     }
}

void BFSTree(AMLGraph G,int v,CSTree &BT) 
{   /*从第v个顶点出发广度遍历图G,建立以BT为根的生成树*/
 int u,w,first,i,j; 
 LinkQueue Q;
 CSTree p,q,r,cur[MAX_VERTEX_NUM];  /*定义指针*/
 r=BT; 
 i=j=0;
 Visited[v]=1;
 InitQueue(Q);
 EnQueue(Q,v);
 while(!QueueEmpty(Q))
   {
    first=1;
    DeQueue(Q,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])
        {
         Visited[w]=1;
         p=(CSTree)malloc(sizeof(CSNode));
         p->data=G.adjmulist[w].data;
         p->firstchild=NULL;
         p->nextsibling=NULL;
         if(first)             /*w是v的第一个未被访问的邻接顶点是根的左孩子结点*/
	   {
	    r->firstchild=p;
	    first=0;
	   }
         else            /*w是v的其他未被访问的邻接顶点是上一邻接顶点的右兄弟结点*/
	   q->nextsibling=p;
         cur[i++]=p;
         q=p;
         EnQueue(Q,w);
        }
    r=cur[j++];
   }
 DestroyQueue(Q);
}

void BFSForest(AMLGraph G,VertexType start,CSTree &BT) 
{ /*建立图G的广度优先生成森树的(最左)孩子(右)兄弟链表BT*/
 int v,w;
 CSTree p,q;
 BT=NULL;
 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])
     {
      p=(CSTree)malloc(sizeof(CSNode));
      p->data=GetVex(G,(v+w)%G.vexnum);
      p->firstchild=NULL;
      p->nextsibling=NULL;
      if(!BT)
        BT=p;
      else
	q->nextsibling=p;
      q=p;
      BFSTree(G,(v+w)%G.vexnum,p);
     }
}

void PrintCSTree(CSTree T,int i)
{ /*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的树*/
 int j;
 CSTree p;
 cout<<ends;
 for(j=1;j<=i;j++)
    cout<<ends<<ends;       /*留出i个空格以表现层*/
 cout<<T->data<<endl;  /*打印元素,换行*/
 for(p=T->firstchild;p;p=p->nextsibling)
    PrintCSTree(p,i+1);  /*打印子树*/
}

void PrintCSForest(CSTree T)
{ /*用凹入表方式打印一棵以孩子-兄弟链表为存储结构的森树*/
 int i=1;
 CSTree p;
 for(p=T;p;p=p->nextsibling)
   {
    cout<<"The "<<i++<<"th tree:"<<endl;
    PrintCSTree(p,0);
   }
}

void SaveGraph(AMLGraph G)
{ /*保存图信息*/
 int i,k;
 char fileName[30];
 VertexType va,vb;
 ofstream outgraph;       /*建立输出文件流对象*/
 cout<<endl<<"Please input the name of graph files:\n";
 cin>>fileName;          /*输入文件名*/
 outgraph.open(fileName,ios::out); /*连接文件,指定打开方式*/
 if(!outgraph)             /*调用重载算符函数测试流*/
   {
    cerr<<"File could not be open."<<endl;
    abort();
   }
 outgraph<<G.vexnum<<endl;          /*向流插入数据*/
 outgraph<<G.edgenum<<endl;
 outgraph<<IncInfo<<endl;
 for(i=0;i<G.vexnum;i++)
   outgraph<<G.adjmulist[i].data<<ends;
 for(k=0;k<G.edgenum;++k)
   {
    va=Edge[2*k];
    vb=Edge[2*k+1];
    outgraph<<endl<<va<<' '<<vb;
   }
 outgraph.close();         /*关闭文件*/
 cout<<"Save the graph successfully.";
}

void LoadGraph(AMLGraph &G)
{  /*从文件加载图*/
 char fileName[30];
 int i,j,k;
 VertexType va,vb;
 ifstream ingraph;   /*建立输入文件流对象*/
 EBox *p;
 cout<<endl<<"Please input the name of graph files:\n";
 cin>>fileName;
 ingraph.open(fileName,ios::in);
 if(!ingraph)
   {
    cerr<<"File could not be open."<<endl;
    abort();
   }
 ingraph>>G.vexnum;         /*提取并测试*/
 ingraph>>G.edgenum;
 ingraph>>IncInfo;
 for(i=0;i<G.vexnum;i++)
   ingraph>>G.adjmulist[i].data;
 for(k=0;k<G.edgenum;++k)
   {
    ingraph>>va>>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;      
    if(IncInfo)
      {
       cout<<"Please input the info :";
       ingraph>>p->info;
      }
   }
 ingraph.close();     /*关闭文件*/
 cout<<"Loatd the graph successfully.";
}

visit(VertexType v)
{ /*输出结点*/
 cout<<ends<<v;
 return OK;
}

void AllPath(AMLGraph G,VertexType start,VertexType nopass,VertexType end,int k)
{ /*寻找路径*/
 int i,w,u,l;
 VertexType temp;
 Path[k]=start;   /*加入当前路径中*/
 l=LocateVex(G,nopass);
 u=LocateVex(G,start);
 Visited[u]=1;
 if(start==end) /*找到了一条简单路径*/
   {
    cout<<ends<<Path[0];
    for(i=1;Path[i];i++)
      cout<<"->"<<Path[i]; /*打印输出*/
    cout<<endl;
   }
 else
   for(w=FirstAdjVex(G,G.adjmulist[u].data);w>=0;
       w=NextAdjVex(G,G.adjmulist[u].data,G.adjmulist[w].data))
     {
      if(w==l)
        continue;     /*如果找到那个不想经过的点,就绕过它,相当不执行后面的语句*/
      if(!Visited[w])
	{
	 temp=G.adjmulist[w].data;
	 AllPath(G,temp,nopass,end,k+1); /*继续寻找*/
	}
     }
 Visited[u]=0;
 Path[k]=0;           /*回溯*/
}

void message()  /*菜单显示*/
{
 cout<<"\n\t\t* * * * * * * * * * * * * * * * * * * *\n";
 cout<<"\t\t*\t1:Creat Graph Manually\t      *\n";
 cout<<"\t\t*\t2:Creat Graph From File\t      *\n";
 cout<<"\t\t*\t3:Dispay The Graph\t      *\n";
 cout<<"\t\t*\t4:BFS The Graph\t\t      *\n";
 cout<<"\t\t*\t5:DFS The Graph\t\t      *\n";
 cout<<"\t\t*\t6:Save Graph To File\t      *\n";
 cout<<"\t\t*\t7:Print All Path\t      *\n";
 cout<<"\t\t*\t8:Destroy The Graph\t      *\n";
 cout<<"\t\t*\t9:Exit\t\t\t      *\n";
 cout<<"\t\t* * * * * * * * * * * * * * * * * * * *\n";
}

void main()
{
 int i,flag;
 VertexType start,nopass,end;
 AMLGraph G;
 CSTree DT,BT;
 cout<<endl;
 cout<<endl;
 cout<<endl;
 cout<<endl;
 cout<<"\t\t* * * * * * * * * * * * * * * * * * * * * * * *\n";
 cout<<"\t\t*\t\t\t\t\t      *\n";
 cout<<"\t\t*  Practice 2.3  The Demo Of Graph Traverse   *\n";
 cout<<"\t\t*\t\t\t\t\t      *\n";
 cout<<"\t\t* * * * * * * * * * * * * * * * * * * * * * * *\n";
 cout<<"\t\t*\t\t\t\t\t      *\n";
 cout<<"\t\t* 04 Computer Science And Technology Class 1  *\n";
 cout<<"\t\t*\t\t\t\t\t      *\n";
 cout<<"\t\t*\t\t  Hu Haihong\t\t      *\n";
 cout<<"\t\t*\t\t\t\t\t      *\n";
 cout<<"\t\t*\t\t  3104006429\t\t      *\n";
 cout<<"\t\t*\t\t\t\t\t      *\n";
 cout<<"\t\t* * * * * * * * * * * * * * * * * * * * * * * *\n";
 cout<<"\n\n\n\t\t\tpress any key to enter the menu……\n";
 getch();
 clrscr(); 
 message();
 cin>>flag;
 while(flag!=9)
   {
    switch(flag)
      {
       case 1: 
               CreateGraph(G);
	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();              
               break;

       case 2: 
               LoadGraph(G);
	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();
               break;
  
       case 3: 
               Display(G);
	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();
               break;
  
       case 4: 
               cout<<"Please input the first vex you want to traverse: ";
               cin>>start;
               cout<<"\t\t\t*******The result of DFSTraverse*******"<<endl;
               cout<<"The Node list of DFSTraverse:"<<endl;
               DFSTraverse(G,start,visit);
               cout<<endl<<"The Egde collection of DFSTraverse:"<<endl;
               DFSForest(G,start,DT);
               PrintAllTraverse(DT);
               cout<<endl<<"Press any key to disply the DFSForest";
               getch();
               cout<<endl<<"The BFSForest of BFSTraverse:"<<endl;
               PrintCSForest(DT);
	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();
               break;

       case 5: 
               cout<<"Please input the first vex you want to traverse: ";
               cin>>start;
               cout<<"\t\t\t*******The result of BFSTraverse*******"<<endl;
               cout<<"The Node list of BFSTraverse:"<<endl;
               BFSTraverse(G,start,visit);
               cout<<endl<<"The Egde collection of BFSTraverse:"<<endl;
               BFSForest(G,start,BT);
               PrintAllTraverse(BT);
               cout<<endl<<"Press any key to disply the BFSForest";
               getch();
               cout<<endl<<"The BFSForest of BFSTraverse:"<<endl;
               PrintCSForest(BT);
	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();
               break;

       case 6: 
               SaveGraph(G);

	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();
               break;       
       case 7:
	       cout<<"Please input the start nod: ";
               cin>>start;

               cout<<"Please input the end nod: ";
               cin>>end;

               cout<<"Please input the node you don't want to pass: ";
               cin>>nopass;

               for(i=0;i<G.vexnum;i++)
                 Visited[i]=0;

	       cout<<"All the paths form "<<start<<" to "<<end
               <<" and don't pass "<<nopass<<" are:"<<endl;
	       AllPath(G,start,nopass,end,0);

	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();
               break;       
       case 8: DestroyGraph(G);

               cout<<"Destroy the Graph successfully!";
	       cout<<endl<<"\t\t**press any key to return the to menu**";
               getch();
               break;   
      }
    getch();
    message();
    cin>>flag;
   }
 DestroyGraph(G);
}