欧拉图算法基础

引言

很多人都玩过“一笔画”游戏，能一笔画成的图要么是所有点的连接变数都是偶数的情况，要么是连接边数是奇数的点有且只有两个的情况，第一种情况从任何点开始都可以完成一笔画，第二种情况只能从其中一个奇数点开始到另一个奇数点结束才能一笔画成。他的原理就是我接下来要介绍的欧拉图（Eular）和欧拉回路（Eular Circuits）。从图论的角度看，有向图和无向图都有欧拉回路的概念，但是判定的方法不一样。

定义

• 通过图中所有边恰好一次且行遍所有顶点的回路称为欧拉回路。具有欧拉回路的无向图称为欧拉图。
• 通过图中所有边恰好一次且行遍所有顶点的通路称为欧拉通路。具有欧拉通路但不具有欧拉回路的无向图称为半欧拉图。
• 欧拉通路和欧拉回路的区别就是起点和终点是否相同。

判别法

1. 对于无向图 G, G是欧拉图当且仅当 G是连通的且没有奇度顶点。
2. 对于无向图 G, G是半欧拉图当且仅当 G是连通的且 G中恰有 0个或 2个奇度顶点。
3. 对于有向图 G , 是欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且每个顶点的入度和出度相同。
4. 对于有向图 , 是半欧拉图当且仅当 G 的所有顶点属于同一个强连通分量且

最多只有一个顶点的出度与入度差为 1 。
最多只有一个顶点的入度与出度差为 1 。
所有其他顶点的入度和出度相同。

无向图的欧拉回路或欧拉路

– 递归版本

void euler(int x) {
    for (int i = head[x]; i; i = Next[i]) {
        if (vis[i])continue;
        vis[i] = vis[i ^ 1] = true, euler(ver[i]);
    }
    ans.push(x);
}

– 非递归版本

void euler() {
    st.push(1);
    while (!st.empty()) {
        int x = st.top(), i = head[x];
        while (i && vis[i])i = Next[i];
        if (i)st.push(ver[i]), vis[i] = vis[i ^ 1] = true, head[x] = Next[i];
        else st.pop(), ans.push(x);
    }
}

– 最小字典序

const int N = 505, M = 1e3 + 30;
int head[N], ver[M << 1], Next[M << 1], tot;
bool vis[M << 1];
stack<int> ans;
int m;

void add(int x, int y) {
    ver[++tot] = y;
    Next[tot] = head[x];
    head[x] = tot;
}

inline bool cmp(int x, int y) {
    return ver[x] < ver[y];
}

void euler(int x) {
    vector<int> tmp;
    for (int i = head[x]; i; i = Next[i])tmp.push_back(i);
    sort(tmp.begin(), tmp.end(), cmp);
    for (auto i:tmp)
        if (!vis[i])vis[i] = vis[i ^ 1] = true, euler(ver[i]);
    ans.push(x);
}

int deg[N];

int main() {
    scanf("%d", &m);
    tot = 1;
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
        deg[x]++, deg[y]++;
    }
    int st = 1;
    for (int i = 1; i <= 500; i++)
        if (deg[i] & 1) {
            st = i;
            break;
        }
    euler(st);
    while (!ans.empty()) {
        printf("%d\n", ans.top());
        ans.pop();
    }
    return 0;
}

例题

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi]表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。 所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。 例如，行程 [“JFK”, “LGA”] 与 [“JFK”,“LGB”] 相比就更小，排序更靠前。 假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

化简题意
我们化简本题题意：给定一个 n 个点 m 条边的图，要求从指定的顶点出发，经过所有的边恰好一次（可以理解为给定起点的「一笔画」问题），使得路径的字典序最小。
这种「一笔画」问题与欧拉图或者半欧拉图有着紧密的联系，
因为本题保证至少存在一种合理的路径，也就告诉了我们，这张图是一个欧拉图或者半欧拉图。我们只需要输出这条欧拉通路的路径即可。

思路及算法
Hierholzer 算法用于在连通图中寻找欧拉路径，其流程如下：

1. 从起点出发，进行深度优先搜索。
2. 每次沿着某条边从某个顶点移动到另外一个顶点的时候，都需要删除这条边。
3. 如果没有可移动的路径，则将所在节点加入到栈中，并返回。

当我们顺序地考虑该问题时，我们也许很难解决该问题，因为我们无法判断当前节点的哪一个分支是「死胡同」分支。
不妨倒过来思考。我们注意到只有那个入度与出度差为 1 的节点会导致死胡同。而该节点必然是最后一个遍历到的节点。我们可以改变入栈的规则，当我们遍历完一个节点所连的所有节点后，我们才将该节点入栈（即逆序入栈）。
对于当前节点而言，从它的每一个非「死胡同」分支出发进行深度优先搜索，都将会搜回到当前节点。而从它的「死胡同」分支出发进行深度优先搜索将不会搜回到当前节点。也就是说当前节点的死胡同分支将会优先于其他非「死胡同」分支入栈。
这样就能保证我们可以「一笔画」地走完所有边，最终的栈中逆序地保存了「一笔画」的结果。我们只要将栈中的内容反转，即可得到答案。

class Solution {
public:
    unordered_map<string, priority_queue<string, vector<string>, std::greater<string>>> vec;

    vector<string> stk;

    void dfs(const string& curr) {
        while (vec.count(curr) && vec[curr].size() > 0) {
            string tmp = vec[curr].top();
            vec[curr].pop();
            dfs(move(tmp));
        }
        stk.emplace_back(curr);
    }

    vector<string> findItinerary(vector<vector<string>>& tickets) {
        for (auto& it : tickets) {
            vec[it[0]].emplace(it[1]);
        }
        dfs("JFK");

        reverse(stk.begin(), stk.end());
        return stk;
    }
};