离散数学实验1 可图画，可简单图化，连通图和欧拉图的判断 C++

• 离散数学实验报告
• • 一、实验题目
  • 二、实验目的
  • 三、实验要求
  • 四、实验步骤和内容
  • • 需求分析：
    • • 输入形式与输入范围
    • 概要设计：
    • • 使用的数据结构与算法：
      • 程序流程：
    • 详细代码
    • 调试分析
    • • 调试过程中所遇到的问题及解决方法
      • 算法的时空分析
  • 五、实验结果
  • 六、实验总结

实验题目：可图画，可简单图化，连通图和欧拉图的判断

实验时间: 2021.12.9

1. 掌握可简单图化的定义及判断方法

2. 掌握连通图、欧拉图的判断方法

3. 掌握欧拉回路的搜索方法

4. 了解欧拉图的实际应用

1. 给定一非负整数序列（例如：(4,2,2,2,2)）

2. 判断此非负整数序列是否是可图化的，是否是可简单图化的

3. 如果是可简单图化的，根据Havel定理过程求出对应的简单图，并输出此简单图的相邻矩阵（默认第i行对应顶点vi）

4. 判断此简单图是否是连通的

5. 如果是连通图，判断此图是否是欧拉图。如果是欧拉图，请输出一条欧拉回路（输出形式如： v 2 − v 1 − > v 5 − > v 3 − > v 4 − > v 5 − > v 2 v_2-v_1->v_5->v_3->v_4->v_5->v_2 v2​−v1​−>v5​−>v3​−>v4​−>v5​−>v2​

对一个度数列判断是否可图化，若可图化则继续判断是否可简单图化，若可简单图化判断是否为欧拉

图，若为欧拉图则输出欧拉回路

预设输入点范围 : 0 < n < 999 0

邻接矩阵的边数： 0 < m < 99 9 2 0

输入形式: 以空格分隔输入的度数 （不含负数）

示例： 4 4 2 2 2

输出：判断是否可图化，若可图化则继续判断是否可简单图化，若可简单图化输出对应Havel算法画出的

图的相邻矩阵，判断是否为欧拉图，若为欧拉图则输出欧拉回路

示例：

**********************************
请输入度数列的长度：(输入0结束程序)
5
请输入度数列：
4 4 2 2 2
可图化  可简单图化

   V1 V2 V3 V4 V5 
V1  0  1  1  1  1 
V2  1  0  1  1  1 
V3  1  1  0  0  0 
V4  1  1  0  0  0 
V5  1  1  0  0  0 

连通

是欧拉图，它的一条欧拉回路是：->V1->V5->V2->V4->V1->V3->V2->V1

相邻矩阵、深度优先遍历、栈、fleury算法

1. 拿到度数列根据度数列之和是否为偶数（握手定理）判断是否可图化，若不可图化程序退出。并且同时判断有无奇数度的点，为判断是否为欧拉图做准备。

2. 若可图化，利用定理4（ check()函数 ）判断是否可简单图化，否则退出程序。

3. 若可简单图化，在Havel定理（ simple()函数 ）运行的过程建立相邻矩阵。

4. 输出相邻矩阵

5. 用深度优先遍历（ bfs()函数 ）判断是否为连通图，并且求出连通分支个数。

6. 若为连通图，根据之前的结果判断是否为欧拉图，反之程序退出

7. 若为欧拉图，利用Fleury算法输出欧拉回路，取第一个点，然后遍历与其连通的边，并判断此边是否为桥，若不为桥则走过这条边，并将其从图中删除，然后对下一个点进行同样的操作，如此递归。注：因为判断是否为桥的时间复杂度太高，我使用了另外一种方法来优化该算法，具体思路如下：

如上图，显然奇数出度的点为1和2，于是我们选择一个点，比如说选择1，那么我们在dfs的过程中，按照dfs的顺序把点的编号放进栈中，比如我们的访问次序是12432，则把12432放入栈中，每经过一条边，就把这条边的正向边反向边打上标记表示这条路已经走过了，由于之前我们已经判过欧拉回路存在的充要条件了，所以请对这张图保持信心，一定是可以找到欧拉回路的，于是我们的算法流程就是：

先把1放到栈中，然后把1-2的边的正向边反向边打上标记，表示已经走过了，然后再把2放到栈中，然后走2-4，打标记，4入栈，走4-3，打标记，3入栈，走3-2，打标机，2入栈，然后我们去走2的时候发现2已经无路可走了，她能走的所有边已经被打上了标记，也就是说这个点已经没有办法出去了，那么什么样的点进去了出不来呢？显然就是我们的奇数出度的点，于是我们在这里把栈顶输出，然后pop出去，然后回溯，每回溯到一个点都判断这个点是否还能走其他边，如果不能走的话，我们就输出这个点，然后再回溯，一直到一个点有其他边可以走，我们就把这个pop，但是不输出，然后再重新从这个点开始dfs比如说这幅图中，我们在dfs了2及右边之后，左边的1由于还有边可以走，于是不输出，从1再开始dfs，最后输出的序列就是2 , 4 , 3，2，1，5 , 6 , 1

#include 
#include 
#include 
#include 
using namespace  std;

int ans[1000];
int idxx;
int sq[1000][1000];
pair d[1000];
pair d2[1000];
bool st[1000];
vector isin;
bool isol= true;
int l=1;
int sum=0;
stackstk;

void search(int x){
    stk.push(x);
    for(int i=1;i<=l;i++){
        if(sq[x][i]){
            sq[i][x]=sq[x][i]=0;
            search(i);
            break;
        }
    }
}
void dfs(int x){
    if(st[x]) return;
    st[x]= true;
    for(int i=1;i<=l;i++){
        if(sq[x][i]) dfs(i);
    }
}
bool check(){
    int lf,rt;
    for(int i=1;i<=l-1;i++){
        lf=rt=0;
        for(int j=1;j<=i;j++){
            lf+=d[j].first;
        }
        rt=i*(i-1);
        for(int j=i+1;j<=l;j++){
            rt+=min(i,d[j].first);
        }
        if(lf>rt) return false;
    }
    return true;
}
void simple(){
    for(int i=1;i<=l;i++){
        int top=d[i].first;
        if(top==0) break;
        for(int j=1;j<=top;j++){
            sq[d[i+j].second][d[i].second]=sq[d[i].second][d[i+j].second]=1;
            d[j+i].first--;
        }
        sort(d+i+1,d+l+1,greater>());
    }
    printf("   ");
    for(int i=1;i<=l;i++){
        printf("V%d ",i);
    }
    cout<
        printf("V%d ",i);
        for(int j=1;j<=l;j++){
            printf(" %d ",sq[i][j]);
        }
        cout<
    stk.push(x);
    while(!stk.empty()){
        int brg=0;
        for(int i=1;i<=l;i++){
            if(sq[stk.top()][i]>0){
                brg=1;
                break;
            }
        }
        if(!brg){
            printf("->V%d",stk.top());
            stk.pop();
        }else {
            int nw=stk.top();
            stk.pop();
            search(nw);
        }
    }
    printf("n");
}
int main() {
    while(1){
        cout<<"nn";
        cout<<"**********************************n";
        cout<<"请输入度数列的长度：(输入0结束程序)n";
        cin>>l;
        sum=0;
        memset(sq,0,sizeof sq);
        isin.clear();
        memset(st,0,sizeof st);
        isol= true;
        cout<<"请输入度数列：n";
        for(int i=1;i<=l;i++){
            int a;
            cin>>a;
            d[i].first=a;
            d2[i].first=a;
            if(a%2) isol= false;
            d[i].second=i;
            d2[i].second=i;
            sum+=a;
        }
        sort(d+1,d+l+1,greater>());
        sum%=2;
        if(sum){
            cout<<"不可图化  ";
            continue;
        }else{
            cout<<"可图化  ";
        }
        if(check()){
            cout<<"可简单图化n"<
                if(!st[i]){
                    fr++;
                    dfs(i);
                }
            }
            if(fr==1){
                printf("n连通n");
                memset(st,0,sizeof st);
                if(isol){
                    printf("n是欧拉图，它的一条欧拉回路是：");
//                    isin.push_back(1);
                    while(stk.size()) stk.pop();
                    fleury(1);
                }else{
                    printf("不是欧拉图");
                }
            }else{
                printf("不连通，连通分支数为%dn",fr);
                continue;
            }
        }else{
            cout<<"不可简单图化n"< 
调试分析 
调试过程中所遇到的问题及解决方法 
一切正常
 
算法的时空分析 
可图化，可简单图化，连通分支数,是否为欧拉图
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         2
        
       
       
        )
       
      
      
       O(n^2)
      
     
    O(n2)
 
欧拉回
    
     
      
       
        O
       
       
        (
       
       
        
         n
        
        
         3
        
       
       
        )
       
      
      
       O(n^3)
      
     
    O(n3)
 
n为顶点数目。
 
五、实验结果 
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-JPNZgDF3-1654332737876)(/Users/a26012/Desktop/截屏2021-12-22 21.12.31.png)]
 
六、实验总结 
心得体会：对领接表，邻接矩阵有了更深的理解，掌握了可图化，可简单图化，判断是否是欧拉图，是否是连通图。很好的锻炼了代码能力，让我深刻意识到自身水平还是很有限，要在未来继续加强代码本领，吸收了许多教训，学到了编程中的许多知识，非常有用。