kkogoro

欧拉路经与欧拉回路
欧拉路经与欧拉回路能够不重复地遍历所有边无向图欧拉路经一个无向图联通并且图中恰好有两个奇数度数顶点,或不存在奇数度...
扫描右侧二维码阅读全文
08
2018/11

欧拉路经与欧拉回路

欧拉路经与欧拉回路

能够不重复地遍历所有边

无向图

欧拉路经

一个无向图联通并且图中恰好有两个奇数度数顶点,或不存在奇数度数顶点,如果存在两个奇数度数顶点,则欧拉路经必然以它们为路径的端点。

欧拉回路

一个无向图联通且不存在奇数度数顶点。

求法

先判断连通性,然后判断是否符合度数限制,如果存在奇数度数的点,则选其中一个点作为dfs起点,如果没有则任选一点作为起点。进行dfs,维护一个记录路径的栈,dfs需要遍历完一个点的所有边后再将这个点入栈,并且需要标记反向边为的是后续dfs不要再走反向边。

最后输出路径就依此弹栈即可。

std::stack<int> s;
void dfs(int u) {
    for (int it = head[u]; it != -1; it = nextEdge[it]) {
        if (vis[it] == false) {
            vis[it] = vis[it^ 1] = true;
            dfs(to[it]);
        }
    }
    s.push(u);
}

有向图

欧拉路径

联通并且所有点的入度和出度都相等或者有一个点的入度出度之差为1,一个点的入度与出度差为-1。

如果存在出入度不同的点,则以这两个点为欧拉路经的起点。

欧拉回路

联通并且所有点的入度和出度

求法

类比无向图

Last modification:November 8th, 2018 at 02:52 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment