欧拉回路欧拉通路欧拉回路图

灰太狼 2021-06-24 15:57 573阅读 0赞

[来源][Link 1]

## **一、定义** ##

**对于无向图：**  
　　1) 设G是**连通**无向图，则称经过G的**每条边一次并且仅一次**的路径为欧拉通路；  
　　2) 如果欧拉通路是**回路**（起点和终点是同一个顶点），则称此回路为欧拉回路（Euler circuit）；  
　　3) 具有欧拉回路的无向图G称为欧拉图（Euler graph）。  
**对于有向图：**  
　　1) 设D是有向图，D的**基图连通**，则称经过D的**每条边一次并且仅一次**的有向路径为有向欧拉通路；  
　　2) 如果有向欧拉通路是**有向回路**，则称此有向回路为有向欧拉回路（directed Euler circuit）；  
　　3) 具有有向欧拉回路的有向图D称为有向欧拉图（directed Euler graph）。

## **二、定理** ##

**无向图：**  
　　无向图G存在欧拉通路的充要条件是：G为**连通**图，并且G\*\*仅有两个奇度结点**（度数为奇数的顶点）或者**无奇度结点\*\*。  
推论：  
　　1) 当G是仅有两个奇度结点的连通图时，G的欧拉通路必以此两个结点为端点。  
　　2) 当G是无奇度结点的连通图时，G必有欧拉回路。  
　　3) G为欧拉图（存在欧拉回路）的充分必要条件是G为无奇度结点的连通图。  
**有向图：**  
　　D为有向图，D的**基图连通**，并且**所有顶点的出度与入度都相等**；或者除两个顶点外，其余顶点的出度与入度都相等，而这两个顶点中一个顶点的**出度与入度**之**差为1**，另一个顶点的出度与入度之**差为-1**。  
推论：  
　　1) 当D除出、入度之差为1，-1的两个顶点之外，其余顶点的出度与入度都相等时，D的有向欧拉通路必以出、入度之差为1的顶点作为始点，以出、入度之差为-1的顶点作为终点。  
　　2) 当D的所有顶点的出、入度都相等时，D中存在有向欧拉回路。  
　　3) 有向图D为有向欧拉图的充分必要条件是D的基图为连通图，并且所有顶点的出、入度都相等。

## **三、算法** ##

**连通性：**  
　　采用深度搜索，如果有节点没有访问，说明不连通。

void DFS(int cur)                     //连通性的判断 是否完全访问掉
    {
        int i ;
        for(i = 0; i<n; i++)
        {
            if(!vis[i]&&edge[cur][i])
            {
                vis[i] = 1;
                DFS(i);
            }
        }
    }
        DFS(0);
        for(int i =0; i<n; i++)
        {
            if(!vis[i])
                return false;
        }

**欧拉图判断：**

# 无向欧拉图：
     for(int i =0; i<n; i++)
     {
         if(degree[i]%2)
         {
             return false;
         }
     }
    # 有向欧拉图：
     for (int i=0; i<n; i++)
        if (in[i] != out[i])
        {
            return false;
        }

**路径查找：**

// 无向图的欧拉回路, cur 点, 从 pos 点开始搜
    void DFS_two(int cur,int pos)
    {
        int i,a,b;
        stack[top++] = cur;
        for(i = pos;i<n;i++)
        {
            if(edge[cur][i] != 0)
            {
                edge[i][cur] = 0;
                edge[cur][i] = 0;
                degree[cur]--;
                degree[i]--;
                DFS_two(i,0);
                break;
            }
        }
        if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步
        {
            b = stack[--top];
            a = stack[--top];
            edge[a][b] = 1;
            edge[b][a] = 1;
            degree[a]++;
            degree[b]++;
            DFS_two(a,b+1);
        }
    
    }

// 有向图的欧拉回路, 在 cur 点, 从 pos 点开始搜
    void DFS_first(int cur ,int pos)
    {
        int i,a,b;
        stack[top++] = cur;
        for(i = pos;i<n;i++)
        {
            if(edge[cur][i] != 0)
            {
                edge[cur][i] = 0;
                out[cur]--;
                in[i]--;
                DFS_first(i,0);
                break;
            }
        }
        if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步
        {
            b = stack[--top];
            a = stack[--top];
            edge[a][b] = 1;
            out[a]++;
            in[b]++;
            DFS_first(a,b+1);
        }
    }

**所有代码：**

#include <stdio.h>
    #include <string.h>
    #include <iostream>
    using namespace std;
    const int MAX = 60;
    int edge[MAX][MAX];
    int degree[MAX];
    int in[MAX],out[MAX];
    int n,type;                           //judge grape 类型
    int e;                                //边数
    int top;                              // 栈底 初始化为 0；
    int stack[MAX];                       //记录欧拉通路的路径
    int vis[MAX];                         //是否已经访问；
    void DFS(int cur)                     //连通性的判断 是否完全访问掉
    {
        int i ;
        for(i = 0; i<n; i++)
        {
            if(!vis[i]&&edge[cur][i])
            {
                vis[i] = 1;
                DFS(i);
            }
        }
    }
    
    
    // 判断是否存在欧拉回路:
    // 无向图中: 连通图且所有顶点度数为偶数
    // 有向图中: 连通图且所有顶点的入度等于出度
    bool judge()
    {
        memset(vis,0,sizeof(vis));        //访问初始化
        DFS(0);
        for(int i =0; i<n; i++)
        {
            if(!vis[i])
                return false;
        }                            //连通性的判断 是否完全访问掉
        if(type)                     //有向图
        {
            for (int i=0; i<n; i++)
                if (in[i] != out[i])
                {
                    return false;
                }
        }
        else                           //无向图
        {
            for(int i =0; i<n; i++)
            {
                if(degree[i]%2)
                {
                    return false;
                }
            }
        }
        return true;
    }
    // 有向图的欧拉回路, 在 cur 点, 从 pos 点开始搜
    void DFS_first(int cur ,int pos)
    {
        int i,a,b;
        stack[top++] = cur;
        for(i = pos;i<n;i++)
        {
            if(edge[cur][i] != 0)
            {
                edge[cur][i] = 0;
                out[cur]--;
                in[i]--;
                DFS_first(i,0);
                break;
            }
        }
        if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步
        {
            b = stack[--top];
            a = stack[--top];
            edge[a][b] = 1;
            out[a]++;
            in[b]++;
            DFS_first(a,b+1);
        }
    }
    // 无向图的欧拉回路, cur 点, 从 pos 点开始搜
    void DFS_two(int cur,int pos)
    {
        int i,a,b;
        stack[top++] = cur;
        for(i = pos;i<n;i++)
        {
            if(edge[cur][i] != 0)
            {
                 edge[i][cur] = 0;
                edge[cur][i] = 0;
    degree[cur]--;
    degree[i]--;
                DFS_two(i,0);
                break;
            }
        }
        if(i==n && top<n)  // 走投无路, 而且还有边的时候, 退回一步
        {
            b = stack[--top];
            a = stack[--top];
            edge[a][b] = 1;
            edge[b][a] = 1;
            degree[a]++;
            degree[b]++;
            DFS_two(a,b+1);
        }
    
    }
    int main()
    {
        printf("0, 无向图 1, 有向图 : ");
        scanf("%d", &type);
        printf("输入顶点个数: ");
        scanf("%d",&n);
        memset(edge,0,sizeof(edge));
        memset(degree,0,sizeof(degree));  //无向图的度数
        memset(in,0,sizeof(in));          //有向图的入度
        memset(out,0,sizeof(out));        //有向图的出度
    
        while(true)
        {
            int a,b;                      //边集
            scanf("%d %d",&a,&b);
            if(!(a||b))                   // 0 0 break
            {
                break;
            }
            edge[a][b] = 1;
            in[b]++;
            out[a]++;
            if(!type)                     // 如果是无向图
            {
                edge[b][a] = 1;
                degree[a]++;                   //无向图的度数
                degree[b]++;
            }
        }
        if(judge())
        {
            printf("\n一条欧拉回路: ");
            if(type)
                DFS_first(0,0);
            else
                DFS_two(0,0);
            for(int i =0; i<top; i++)
            {
                printf("%d",stack[i]);
                if(i+1!=top)
                    printf(" -> ");
            }
            putchar('\n');
        }
        else
        {
            printf("\n不存在欧拉回路!\n");
        }
        return 0;
    }

[Link 1]: http://www.cnblogs.com/locojyw/p/3724562.html