flury.txt

求欧拉回路的弗洛里算法

//------------------------------------------------------------------------------
//调用头文件及地址空间 
//------------------------------------------------------------------------------
#include <cstdio>
#include <string>
#include <iostream>
#include <cstdlib>
using namespace std; 


//------------------------------------------------------------------------------
//建立全局变量，用来存储顶点个数 
//------------------------------------------------------------------------------
static int nValue;

//------------------------------------------------------------------------------
//建立全局变量，用来存储边的个数 
//------------------------------------------------------------------------------
static int side;            

           
//------------------------------------------------------------------------------
////建立边的邻接矩阵 mapE 50×50  
//------------------------------------------------------------------------------
int mapE[50][50];   


//------------------------------------------------------------------------------
//建立顶点的堆栈G(V)
//------------------------------------------------------------------------------
struct stack                                
{  
    int top;                                  //栈顶 
    int base;                                 //栈底 
    int Ddian[50];
}V;      


//------------------------------------------------------------------------------
//主函数main 
//------------------------------------------------------------------------------
int main(int argc, char *argv[])          
{

    void Oular(int);                          //声明函数Oular 
    void DvsMap(int);                         //声明函数DvsMap 
    bool judge(int&);                         //声明函数judge 
    
    int vi,vj,begain;                         //定义变量 
    
    for(int p=0;p<50;p++)                     //清空图的连接表 
        for(int k=0;k<50;k++)
           mapE[p][k]=0;   
           
    cout<<"请输入顶点数：";                    //读入顶点个数 
    cin>>nValue;
    cout<<"请输入边数：";                      //读入边的个数 
    cin>>side;                      

    int i;                                    //i计数 
    cout<<endl<<"共"<<side<<"条边!"<<endl; 
    for(i=0;i<side;i++){                      //写入边的信息 
        cout<<"输入第"<<i+1<<"条:"; 
        cin>>vi;
        cin>>vj;                          
        mapE[vi][vj]=1;                       //1代表存在此边 
        mapE[vj][vi]=1;                        //无向图            
        }

    begain=1;                                  
    if(1==judge(begain))                      //判断是否存在欧拉回路
        Oular(begain);                         //存在欧拉图，调用函数Oular 
    else cout<<endl<<"不存在欧拉回路！";        //否则输出不存在 
    
    cout<<endl;
    system("PAUSE"); 
    return EXIT_SUCCESS;
}


//------------------------------------------------------------------------------
//子函数DvsMap：图的深度优先遍历
//------------------------------------------------------------------------------ 
void DvsMap(int dot)                      
{
     V.top++;
     V.Ddian[V.top]=dot;

     for(int k=1;k<=nValue;k++)
         if(1==mapE[k][dot]&&k!=dot){          //先排除环的情况，待最后输出时加入 
               mapE[k][dot]=0; 
               mapE[dot][k]=0;
               DvsMap(k);
               break;
         }
}


//------------------------------------------------------------------------------
//子函数Oular：欧拉回路算法
//------------------------------------------------------------------------------
void Oular(int dot)   
{
     int i,b;
     V.top=0;
     V.Ddian[V.top]=dot;                      //压栈

     cout<<endl<<"找到欧拉回路:";
     while(V.top>=0){                         //通过此循环和DvsMap组合将桥变成唯一选择，从而可以不进行桥的判断
          b=0;
          for(int i=1;i<=nValue;i++) 
              if(1==mapE[V.Ddian[V.top]]&&V.Ddian[V.top]!=i){
                 b=1;
                 break;
                 }
          if(0==b){                           //如果是平凡图或没有可用点，输出并从栈中删除 
             cout<<V.Ddian[V.top]<<"-->";
             if(1==mapE[V.Ddian[V.top]][V.Ddian[V.top]]){       //考虑是否是环 
                     cout<<V.Ddian[V.top]<<"-->";                  //是则输出环 
                     mapE[V.Ddian[V.top]][V.Ddian[V.top]]=0;       //从边的表中删除此环 
                     }
             V.top--;
             }
          else{                               //如果有可用点，就调用函数DvsMap 
               V.top--;
               DvsMap(V.Ddian[V.top+1]);
               }    
    }
    cout<<"Over."; 
}


//------------------------------------------------------------------------------
//子函数judge：判断是否存在欧拉回路 
//------------------------------------------------------------------------------
bool judge(int &begain)
{
    int j,i,vk,num;
    vk=0;                                      //奇度点计数 
    for (i=1;i<=nValue;i++){          
        num=0;
        for(j=1;j<=nValue;j++)
              if(i!=j)                         //先排除环的情况，待最后输出时加入 
              num=mapE[j]+num;
        if(num%2==1){
              begain=i;
              vk++;
        }
    }
    if((0==vk)||(2==vk))                       //0奇度点是欧拉图，2奇度点是半欧拉图 
        return 1;                              //存在欧拉图或半欧拉图,返回1 
    else return 0;                             //不存在欧拉图，返回0 
}