有向图的深度遍历.cpp

有n个选手 P 1 ,P 2 ,P 3 ,… ,P n 参加了的单循环赛

/*有向图的邻接表的相关算法
  时间:2008.09.10
  版本:v2.0
*/
#include   <iostream.h>
#include   <stdlib.h>
typedef  int  VertexType ;          //顶点数据类型
#define   MAX_VERTEX_NUM   20         //最大顶点数
#define   MAX_EDGE_NUM   40          //最大边数
int   visited[MAX_VERTEX_NUM];       //访问标志数组
/*结点类型*/
struct   ArcNode
{
   int   adjvex;           //该弧所在的顶点位置
   ArcNode   *nextarc;       //指向下一条弧
};
/* 表头结点定义*/
struct   VNode
{
   VertexType   data;           //顶点信息
   ArcNode   *firstarc;         //指向第一条弧
};
typedef VNode AdjList[MAX_VERTEX_NUM];
/*图定义*/
struct ALGraph
{
    AdjList  vertices;
    int   vexnum,arcnum;
};
ALGraph  G;
void   CreateDG(ALGraph   &G)
{
  int   i,j,k;
  ArcNode   *p;
  cout<<"创建一个有向图:"<<endl;//也就是依次输入N个选手的胜负情况
  cout<<"顶点数:"<<endl;   cin>>G.vexnum;     //选手数N
  cout<<"边数:"<<endl;     cin>>G.arcnum;   //选手比赛次数,由于是单循环肯定是N*(N-1)*/2盘比赛
  /*        初始化        */
  for(i=1;i<=G.vexnum;i++)
  {
     G.vertices[i].data=i;
     G.vertices[i].firstarc=NULL;
  }
  for(k=0;k<G.arcnum;k++)
  {
     cout<<"请输入第"<<k+1<<"条边:";
     cin>>i>>j;
     p=new ArcNode;
     p->adjvex=j;
     p->nextarc=G.vertices[i].firstarc;
     G.vertices[i].firstarc=p;
   }
}
void   Disp(ALGraph G)
{
   int   i;
   ArcNode   *p;
   cout<<"输出图为:"<<endl;
   for(i=1;i<=G.vexnum;i++)
   {
     p=G.vertices[i].firstarc;
     while(p!=NULL)
     {
         cout<<"("<<i<<","<<p->adjvex<<")";
         p=p->nextarc;
     }
    cout<<endl;
   }
   cout<<"*******************************"<<endl;
}
int  dfs(int v)   //深度优先遍历
{
  int count=0;
  ArcNode *p=new ArcNode;
    cout<<G.vertices[v].data<<"＊＊＊";
  count++;
  visited[v]=1;
  p=G.vertices[v].firstarc;
  while(p!=NULL)
  {
    if(!visited[p->adjvex])

    count=dfs(p->adjvex)+1;
    p=p->nextarc;
   }
 return count;
}
int   main()
{
  int visited[20];
  int v;
  int count;
  char flag;//是否继续搜索
  bool isshow=true;//判断是否满足要求
  CreateDG(G);
  Disp(G);

      for(int i=1;i<G.vexnum;i++)
      {visited[i]=0;}
     for(int v=1;v<G.vexnum;v++)
     {
        if( dfs(v)==G.vexnum)
        {
           cout<<endl;
           cout<<"这条满足要求";
           break;
        }
        cout<<endl;
     }
  cout<<"程序结束!"<<endl;
}


 /* for(;;)//只要深度遍历能把所储存的顶点都依次输出就得到了要求的序列,当然根据情况有可能不只一条
  {
      for(int i=1;i<G.vexnum;i++)
      {visited[i]=0;}
     cout<<"请输入深度优先搜索的顶点:";
     cin>>v;cout<<endl;
     cout<<"深度优先序列:";
     //if(isshow=dfs(v))
    // {
        cout<<dfs(v);
        cout<<endl;
       // cout<<"该序列满足要求!"<<endl;
    // }
     //else
     //{
        cout<<endl;
        //cout<<"该序列不满足要求!"<<endl;
     //}
     cout<<endl;
     cout<<"是否结束搜索?(Y/N)"<<endl;
     cin>>flag;
     if(flag=='Y')
     {
        break;
     }
  }  */