求欧拉图G=的欧拉回路

albert-biu 2021-08-07 原文

【实验目的】

通过算法设计并编程实现，使学生掌握利用计算机语言实现欧拉图的判定和欧拉回路的求解方法。

【实验内容】

给定n个结点的无向图G=<V, E>的邻接矩阵，可判断该图是否是欧拉图，如果是欧拉图，请给出欧拉回路。

【实验原理和方法】

判定图G是否是欧拉图

欧拉图的判定定理

求欧拉图G=<V,E>的欧拉回路

设G为欧拉图，一般说来G中存在若干条欧拉回路，下面是求欧拉回路的Fleury算法：

（1）任取v0∈V(G)，令P0=v0；

（2）设Pi=v0e1v1e2…eivi已经行遍，按下面方法来从E(G)-{e1,e2,…,ei}中选取ei+1：

（a）ei+1与vi想关联；

（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-{e1,e2,…,ei}中的桥.

（3）当（2）不能再进行时，算法停止。

【实验环境及工具】

运行Windows 或Linux操作系统的PC机，任意软件开发语言C，C++，Java等及相应的开发环境。

【测试用例】

[数据输入]

边数5，点数6

相关联的点1 2

1 3

2 5

4 2

3 2

4 5

[数据输出] 存在欧拉回路 1，3，2，4，5，2，1

恩，Fleury（弗洛莱）算法，

#include "bits/stdc++.h"

using namespace std;
const int maxn = 1e3;
int vis[maxn][maxn];
int n, m, x, y;
vector<int> e[maxn];
deque<int> q;

void addEdge(int a, int b) {
    e[a].push_back(b);
    e[b].push_back(a);
}

bool dfs(int now, int sum) {
    if (sum == m) {
        while (!q.empty()) {
            cout << q.back() << " ";
            q.pop_back();
        }
        cout << endl;
        return 1;
    }
    for (int i = 0; i < e[now].size(); i++) {
        if (!vis[now][e[now][i]]) {
            vis[now][e[now][i]] = 1;
            vis[e[now][i]][now] = 1;
            q.push_front(e[now][i]);
            if (dfs(e[now][i], sum + 1))
                return 1;
            q.pop_front();
            vis[now][e[now][i]] = 0;
            vis[e[now][i]][now] = 0;
        }
    }
    return 0;
}

int main() {
    //freopen("input.txt", "r", stdin);
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        cin >> x >> y;
        addEdge(x, y);
    }
    q.push_front(1);
    if (!dfs(1, 0))
        cout << "NO answer" << endl;
    return 0;
}