欧拉路径与哈密顿路径

欧拉路

1、欧拉路径：从某一点出发经过一条不间断的路径，这条路径刚好访问整个图的所有边一次且仅一次(一笔画问题)。一个图可能有多条欧拉路径
2、欧拉回路：一条首尾相接的欧拉路径(首尾相接的一笔画问题)。一个图可能有多条欧拉回路
3、欧拉图：具有欧拉回路的图。特点为：无向图中所有顶点的度都是偶数；有向图中所有顶点的入度和出度都相等
4、半欧拉图：具有欧拉路径但不具有欧拉回路的图。特点为：无向图中有且仅有两个顶点的度为奇数，这两个顶点分别为起点和终点；有向图中有且仅有一个顶点的出度 - 入度 $= 1$，另有且仅有一个顶点的入度 - 出度 $= 1$，这两个顶点分别为起点和终点
5、推论：欧拉图的所有欧拉路径都是欧拉回路，所以计算欧拉回路与欧拉路径的算法完全一样
6、无向图中，在欧拉路的 2 个奇数度点之外，每多有 2 个奇数度点，画完所需要最少的笔数增加一笔

哈密顿路径

1、

Fleury 算法

Fleury 算法

1、预先判断给定的图是不是欧拉图或半欧拉图
2、选择起点。对于欧拉图：起点任意。对于半欧拉图：如果是无向图，选择任意奇数度点；如果是有向图，选择出度 - 入度 $= 1$ 的点
3、从起点开始，向外选择一条边，这条边应与该点相连且应优先选择不是桥的边(桥：删除后不会将图分割为两个连通分量的边，即不会将图分为两个独立部分)。再从新的点继续该操作，直至无法进行为止
4、这种算法的复杂度较高，通常应使用下面的 Hierholzer 求欧拉路

Hierholzer 算法

Hierholzer 算法

1、预先判断给定的图是不是欧拉图或半欧拉图
2、选择起点。对于欧拉图：起点任意。对于半欧拉图：如果是无向图，选择任意奇数度点；如果是有向图，选择出度 - 入度 $= 1$ 的点
3、初始化设置答案栈 $ans$，存储走过路径途径的节点。对图进行 DFS，允许点重复经过，每访问一条边就将其删掉，然后对这条边另一端的节点进行遍历。当一个节点完成遍历且没有相连边时，将该节点入栈，并回溯到上一层
4、遍历结束后，将 $ans$ 中的节点依次出栈，得到的就是欧拉路径/欧拉回路的节点访问顺序
5、为了方便实现，在此先使用邻接矩阵建图，实现最简单的功能。复杂度很高，需要优化

无向图代码实现

const int N = 1e4 + 10;
int n; // 点的个数

bitset<N> g[N]; // 邻接矩阵建图
int deg[N];     // 存储每个点的度
stack<int> stk; // 存储答案路径

// 获取每个点的度
void get_degree()
{
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (g[i][j])
                deg[i]++, deg[j]++; // 无向图中 i、j 各有 1 度
}

// 获取起点
int get_start()
{
    int ct = 0, st = 1;
    for (int i = 1; i <= n; i++)
    {
        // 如果度为奇数
        if (deg[i] % 2)
        {
            ct++;
            st = i;
        }
        // 有 2 个以上奇数度点，不存在欧拉路径
        if (ct > 2)
            return -1;
    }
    return st;
}

// DFS 与 Hierholzer
void Hierholzer(int x)
{
    for (int y = 1; y <= n; y++)
    {
        if (g[x][y])
        {
            g[x][y] = g[y][x] = 0; // 删除边
            Hierholzer(y);         // DFS
        }
    }
    stk.push(x);
}

有向图代码实现

const int N = 1e4 + 10;
int n; // 点的个数

bitset<N> g[N]; // 邻接矩阵建图
int deg[N];     // 存储每个点 入度-出度 的差
stack<int> stk; // 存储答案路径

// 获取每个点的度
void get_degree()
{
    for (int i = 1; i < n; i++)
        for (int j = i + 1; j <= n; j++)
            if (g[i][j])
                deg[i]--, deg[j]++; // 有向图，i 出度 -1，j 入度 +1
}

// 获取起点
int get_start()
{
    int plus_one = 0, minus_one = 0, st = 1;
    for (int i = 1; i <= n; i++)
    {
        // 统计入度 - 出度 = 1 的次数
        if (deg[i] == 1)
            plus_one++;
        // 统计出度 - 入度 = 1 的次数
        else if (deg[i] == -1)
        {
            minus_one++;
            st = i; // 作为起点
        }
        // 非以上情况且非 0，不存在欧拉路径
        else if (deg[i] != 0)
            return -1;
    }

    // 所有点入度 = 出度 或 有且仅有一个 plus 和 minus 时有欧拉路径
    if ((plus_one == 0 && minus_one == 0) || (plus_one == 1 && minus_one == 1))
        return st;
    else
        return -1;
}

// DFS 与 Hierholzer
void Hierholzer(int x)
{
    for (int y = 1; y <= n; y++)
    {
        if (g[x][y])
        {
            g[x][y] = 0;   // 删除边，注意有向图只删除 x->y
            Hierholzer(y); // DFS
        }
    }
    stk.push(x);
}

欧拉路径与哈密顿路径

Fleury 算法

Hierholzer 算法

页底评论