none
广度遍历和深度遍历的问题 RRS feed

  • 常规讨论

  • 程序要求:

    Description

    编写无向图的邻接矩阵类AdjMWGraph,实现无向图的广度遍历和深度遍历。其中,图中顶点数据类型为字符。

    Input

    第一行图中顶点的个数
    第二行是图中边的条数
    第三行是顶点信息
    后面的输入数据是依附于一条边的两个顶点,有多少条边,就输入多少组信息。

    Output

    广度优先搜索序列。
    深度优先搜索序列。

    Sample Input

    7
    6
    A B C D E F G
    A B 
    A C
    B D
    B E
    C F
    C G

     

    Sample Output

    A B C D E F G
    A B D E C F G

     

     

    代码:
    #include<iostream>
    #include<stdlib.h>
    using namespace std;

    const int MaxQueueSize=100;

    template<class T>
    class SeqQueue
    {
     T data[MaxQueueSize];    //在此用的是静态数组
     int front;        //队头指示
     int rear;         //队尾指示
     int count;     //当前元素个数计数器
    public:
     SeqQueue(void)    //构造函数:用以构造空队列
     { front=rear=0; count=0; }
     ~SeqQueue(void)  //析构函数
     {  }

     void QInsert(const T& item); //入队
     T QDelete(void);             //出队
     T QFront(void) const;        //读队头元素
     bool QueueEmpty(void) const   //判别是否为空队
     {  return (count==0);  }
     void ClearQueue(void)       //清空队列
     {
      front=rear=0;
      count=0;
     }
     int GetSize(void) const    //读队列长度(所含元素个数)
     { return count; }
    };

    template<class T>
    void SeqQueue<T>::QInsert(const T& t)  //入队
    {
     if(count==MaxQueueSize)  //检查队列是否已满
     {
      cerr<<"队列已满!"<<endl;
      exit(1);
     }
     data[rear]=t;   //入队
     rear=(rear+1) % MaxQueueSize;  //修改队尾
     count++;    //元素个数增1
    }

    template<class T>
    T SeqQueue<T>::QDelete()   //出队
    {
     T temp;
        if(count==0)      //检查队列是否已空
     {
      cerr<<"队列已空!"<<endl;
      exit(1);
     }
     temp=data[front];         //取出队头元素
     front=(front+1)% MaxQueueSize;  //修改队头指示
     count--;
     return temp;
    }

    template<class T>
    T SeqQueue<T>::QFront(void) const  //读队头元素
    {
       if(count==0)
     {
      cerr<<"队列已空!"<<endl;
      exit(1);
     }
       return data[front];
    }
    const int MaxSize=20;      
    template<class T>
    class AdjMWGraph            //AdjMWGraph<T>类的定义
    {
    private:
        char vexs[MaxSize];
     int arcs[MaxSize][MaxSize];
        int vexnum;
        int arcnum;
    public:
     void GouZhaojuzhen( ) ;
        int GetFirstNeighbor(const int i);
     int GetNextNeighbor(const int v1,const int v2);
        void DepthFirstSearch(const int v,bool visited[]);
     void BroadFirstSearch(const int v,bool visited[]);
     
        int Locatevex(char v1);
    };
    template<class T>
    void AdjMWGraph<T>:: GouZhaojuzhen( )
    {
    int i,j,k;
    char v1,v2;
    cin>>vexnum;
    cin>>arcnum;
    for (i=0;i<vexnum;++i)  cin>>vexs[i];
    for (i=0;i<vexnum;++i)
     for(j=0;j<vexnum;++j)
          arcs[i][j]=0;
    for (k=0;k<arcnum;++k)
    {cin>>v1>>v2;
    i=Locatevex(v1); j=Locatevex(v2);
    arcs[i][j]=1;
    arcs[j][i]=arcs[i][j];}
    }
    template<class T>
    int AdjMWGraph<T>::GetFirstNeighbor(const int v)
    {
     
     if(v<0||v>vexnum)
     {
      cout<<"参数v越界!"<<endl;
      exit(1);
     }
     for(int col=0; col<vexnum; col++)
     
      if(arcs[v][col]>0)
      return col;
     
     return -1;
    }

    template<class T>
    int AdjMWGraph<T>::GetNextNeighbor(const int v1,const int v2)
    {
     int i=-1;
     if(v1<0||v1>vexnum||v2<0||v2>vexnum)
     {
      cout<<"参数v1或v2越界!"<<endl;
      exit(1);
     }
     for(int col=v2+1; col<vexnum; col++)
          if( arcs[v1][col]>0)
        {
         i=col;
         break;      //找到了,退出循环
        }
     return i;
    }

    template<class T>
    void AdjMWGraph<T>::DepthFirstSearch(const int v,bool visited[])
    {
     cout<<vexs[v]<<""; 
     visited[v]=true;   
       
     int w=GetFirstNeighbor(v);

     while(w!=-1)
     {
      
      if(!visited[w]) DepthFirstSearch(w,visited);
      w=GetNextNeighbor(v,w);  
     }
    }

    template<class T>
    void AdjMWGraph<T>::BroadFirstSearch(const int v,bool visited[])
    {//广度优先搜索遍历
     T u,w;
     SeqQueue<T> queue;    //申明一个空队列

     cout<<vexs[v]<<"";  //访问v
     visited[v]=true;     //作相应的标记

     queue.QInsert(v);         //v入队
     while(!queue.QueueEmpty())
     {
      u=queue.QDelete();     //出队一个顶点记为u
      w=GetFirstNeighbor(u); //求u的第一个邻接顶点w
      while(w!=-1)   //当w存在
      {
       if(!visited[w])    //如果它没有被访问过
       {
        cout<<vexs[w]<<"";  //访问它
        visited[w]=true;    //作相应的访问标记
        queue.QInsert(w);   //让w入队
       }
       w=GetNextNeighbor(u,w);  //求u的下一个邻接顶点
      }
     }
    }

     

    template<class T>
    int AdjMWGraph<T>:: Locatevex(char v1 )
    {
        int i=0;
     for(i;i<vexnum;++i)
      if(vexs[i]==v1)break;
     return i;
    }
     
    int main( )
    {
    AdjMWGraph <char>G;
    int v=0;

    bool visited[MaxSize];

      G.GouZhaojuzhen( );
      G.DepthFirstSearch(v , visited);
      cout<<endl;
      G.BroadFirstSearch(v,visited);
      return 0;
    }
    不能得到预期的结果,请大家帮我看看,问题出在哪里?

    2009年5月13日 17:45

全部回复