admin 管理员组

文章数量: 888526

有向图的欧拉回路

有向图的欧拉回路定义和证明

有向图的euler回路定义：经过图中每条边一次且仅一次并且行遍图中每个顶点（顶点可以多次）的回路。

算法导论22-3里需要证明有向强连通图G有euler回路，当且仅当每个节点的入度等于出度。
证明：=> 若有向强连通图G有euler回路，则可知对于出发点s，假设有x次从s出，那么要想最后回到s，则必须得恰好回到s点x次，因此对于出发点s，入度出度必然相等；假设对于某个非出发点v，若它的出度与入度不相等：假设出度y大于入度x，则第x次从v离开之后就再也不能回到v，则剩余的y-x条出边不能被访问到；假设出度y小于入度x，则第y+1次进入v后无法出去；由此可知，对与非出发点v，其入度与出度同样相等。因此图G有euler回路，每个节点v的入度等于出度成立。
<= 假设有向强连通图G的每个节点的入度等于出度，则从出发点s开始遍历（每条边只能经过一次，但点可以经过多次），最终必然会回到出发点s（不一定每个节点都走过），这是因为，如果最终没有回到出发点，则会有一条s->v1->v2->…->vi的路径，其中vi不等于s，这就可知遍历过程中进入vi的次数比从vi走出的次数多一次，这样就肯定至少有一条从vi出的边没有被访问到，所以不成立，因此可知从出发点s开始遍历，最终必然会回到出发点s。这样遍历一次之后会形成一个子回路，这样在该子回路上的某异与s点的点s1开始继续遍历，会形成一个以s1为起始点（也即终止点）的子回路，这两个回路没有公共边，而这两个子回路明显可以合并为一个回路，该回路为s->…->e->s1->f->…->s1->…->s，这样不断扩展下去必然可以形成一个euler回路，证毕。

算法思想

从起点s出发搜索回路C，设C = s->…x->s，当s的所有出边已访问时，将顶点s压栈，递归函数euler(u)回升到顶点x，继续探索顶点x未访问的边，直到递归回升到起点s。最后将顶点栈S中的顶点v依次弹出，即为一条以s为起点的欧拉回路。

EULER-CIRCLE() //搜索有向图的欧拉回路EULER(s) //从起点s开始搜索欧拉回路while(S is not empty)v = S.pop()list = list.add(v)//添加到顶点链表return list;//欧拉回路的顶点序列

EULER(u) //递归的搜索欧拉回路for each v in adj[u]	//对于顶点u的每一条出边e = (u, v)e = (u, v)if e.visited == falsethen e.visited = tureEULER(v) //从顶点v出发继续搜索push(S, e) //对于有平行边的图，可考虑将边e压栈push(S, u) //当顶点u的所有出边已访问时，将顶点u压入栈S中

下图的例子说明算法的工作过程：
有向图 G = <V, E>
V = {a, b, c, d}
E = {<a, b>, <a, d>, <b, c>, <c, a>, <c, d>, <d, a>, <d, c>}
栈S中的顶点（按进栈次序排列）：a d c d a c b a
出栈次序：a b c a d c d a
欧拉回路：a ->b->c->a->d->c->d->a

算法实现

package graph;import java.util.ArrayList;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Stack;public class AdjListDirectedGraph<V, E> {private Vertex<V>[] adj;// 邻接表private int n;// 顶点数目private int time = 0;private int sccNum;// 强连通分量数目private int[] scc;// 顶点v的强连通分量编号private int[] dfn;// dfs发现时间private int[] low;// 可追溯的最小dfn顶点private int[] parent;// 在深搜树中的父节点private Stack<Integer> stack;// 顶点栈@SuppressWarnings("unchecked")AdjListDirectedGraph(int capacity) {adj = new Vertex[capacity];n = 0;}public void addVertex(int v, V value) {adj[v] = new Vertex<>(value);n++;}public void addEdge(int u, int v) {addEdge(u, v, null);}public void addEdge(int u, int v, E value) {Edge prev = null;//for (Edge curr = adj[u].first; curr != null; curr = curr.next) {if (v == curr.v) {curr.value = value;return;} else if (v < curr.v) {if (prev == null) {adj[u].first = new Edge<E>(u, v, value, curr);} else {prev.next = new Edge<E>(u, v, value, curr);}return;}prev = curr;}// 插入到链表尾部if (prev == null) {adj[u].first = new Edge<E>(u, v, value, null);// 第一个边结点} else {prev.next = new Edge<E>(u, v, value, prev.next);// 插入到边链表的尾部}}public void findEulerTour() {LinkedList<Integer> tour = new LinkedList<>();eulerTour(tour);ListIterator<Integer> itr = tour.listIterator();StringBuffer sb = new StringBuffer(tour.size());int v;if (itr.hasNext()) {// 路径起点v = itr.next();// 顶点vsb.append(adj[v].value);}while (itr.hasNext()) {v = itr.next();// 顶点vsb.append("->" + adj[v].value);}System.out.println(sb);}public boolean eulerTour(LinkedList<Integer> tour) {// assume tour != nullif (n == 0 || stronglyConnectedComponent() > 1) {return false;// 空图或者有向图G非强连通}int[] indegree = new int[n];// 入度int[] outdegree = new int[n];// 出度for (int u = 0; u < n; u++) {for (Edge e = adj[u].first; e != null; e = e.next) {int v = e.v;// <u, v>outdegree[u]++;indegree[v]++;}}boolean flag = true;for (int u = 0; u < n && flag; u++) {flag = flag && (outdegree[u] == indegree[u]);}if (!flag) {return false;// 不存在欧拉回路}initialize();euler(0);while (!stack.isEmpty()) {tour.add(stack.pop());}return true;}/*** 从顶点u出发，沿未经过的边搜索* * @param u*/@SuppressWarnings("unchecked")void euler(int u) {// 可考虑使用边迭代器，itr[u]表示顶点u的出边表迭代器，itr[u].next()获取下一条未经过的边，// 同一个顶点u对应的多个递归实列euler(u)使用同一个迭代器itr[u]，快速取出下一条未经过的边e。for (Edge e = adj[u].first; e != null; e = e.next) {int v = e.v;if (!e.visited) {// e未经过e.visited = true;euler(v);}}// 顶点u的所有出边已被探寻stack.push(u);}public void printAdjList() {StringBuilder vs = new StringBuilder();StringBuilder es = new StringBuilder();boolean wrc = false;vs.append("{");es.append("{");for (int i = 0; i < n; i++) {vs.append(adj[i].value);if (i < n - 1) {vs.append(", ");}for (Edge p = adj[i].first; p != null; p = p.next) {if (wrc)es.append(", ");es.append("(");es.append(adj[i].value);es.append(", ");es.append(adj[p.v].value);es.append(")");wrc = true;}}vs.append("}");es.append("}");System.out.println(vs);System.out.println(es);}void initialize() {time = 0;sccNum = 0;parent = new int[n];dfn = new int[n];low = new int[n];scc = new int[n];stack = new Stack<>();for (int u = 0; u < n; u++) {parent[u] = -1;dfn[u] = 0;low[u] = 0;scc[u] = 0;for (Edge e = adj[u].first; e != null; e = e.next) {e.visited = false;}}}public int stronglyConnectedComponent() {initialize();// 初始化搜索信息for (int u = 0; u < n; u++) {if (dfn[u] == 0) {tarjan(u);// 从顶点u开始搜索}}return sccNum;}@SuppressWarnings("unchecked")void printConnectedComponent() {ArrayList<Integer>[] components = new ArrayList[sccNum + 1];// [1..sccNum]for (int i = 1; i <= sccNum; i++) {components[i] = new ArrayList<>();// 第i个连通分量}for (int u = 0; u < adj.length; u++) {components[scc[u]].add(u);}// 打印每个连通分量for (int i = 1; i <= sccNum; i++) {System.out.print("{");for (int j = 0; j < components[i].size(); j++) {int v = components[i].get(j);// 顶点vSystem.out.print(adj[v].value);if (j < components[i].size() - 1) {System.out.print(", ");}}System.out.print("}");System.out.println();}}/*** tarjan算法计算顶点low值和有向图的强连通分量* * @param u*/void tarjan(int u) {dfn[u] = ++time;low[u] = dfn[u];stack.push(u);// 顶点u进栈for (Edge e = adj[u].first; e != null; e = e.next) {int v = e.v;// <u, v>if (dfn[v] == 0) {// 顶点未被访问parent[v] = u;tarjan(v);// 从顶点v继续搜索if (low[v] < low[u]) {// 顶点u的后代可追溯的最早栈中顶点low[u] = low[v];}} else if (scc[v] == 0) {// 顶点v已进栈, 尚未出栈// if v in stack S, then low[u] = min {low[u], dfn[v]}// case #1: <u, v> 是反向边，顶点v在栈中// case #2: <u, v> 是交叉边，如果v所属的强连通分量scc[v]未访问，则v在栈中// case #3: <u, v> 是交叉边，如果v所属的强连通分量scc[v]已访问，则v不在栈中// case #4: <u, v> 是前向边，无论v是否在栈中，low[u] <= dfn[u] < dfs[v], 所以不会更新low[u]if (dfn[v] < low[u]) {// 顶点u自己可追溯的最早栈中顶点low[u] = dfn[v];}}}if (low[u] == dfn[u]) {// 强连通分量C对应的深搜树根usccNum++;int x;while ((x = stack.pop()) != u) {scc[x] = sccNum;}scc[x] = sccNum;// x = u}}static class Edge<E> {int u;// <u, v>int v;E value;Edge<E> next;// 顶点u相同的下一条边boolean visited;// 标记Edge(int u, int v, E value, Edge<E> next) {super();this.u = u;this.v = v;this.value = value;this.next = next;}@Overridepublic String toString() {return "<" + u + ", " + v + ">";}}static class Vertex<V> {V value;Edge first;// 第一条边Vertex(V value) {super();this.value = value;}@Overridepublic String toString() {return "" + value + "";}}}

测试代码

package graph;import java.util.Scanner;
import java.util.regex.Matcher;
import java.util.regex.Pattern;public class TestAdjListDirectedGraph {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();// 顶点数int m = in.nextInt();// 边数in.nextLine();AdjListDirectedGraph<Character, Object> graph = new AdjListDirectedGraph<>(n);for (int i = 0; i < n; i++) {graph.addVertex(i, (char) ('a' + i));}Pattern pattern = Pattern.compile("<([a-z]), ([a-z])>");// <u, v>for (int i = 0; i < m; i++) {String s = in.nextLine();Matcher matcher = pattern.matcher(s);while (matcher.find()) {// pair (u, v)int u = matcher.group(1).charAt(0) - 'a';int v = matcher.group(2).charAt(0) - 'a';graph.addEdge(u, v);}}graph.findEulerTour();}}

测试案例

test case #1:
input:
4 7
<a, b>
<a, d>
<b, c>
<c, a>
<c, d>
<d, a>
<d, c>

result:
a->b->c->a->d->c->d->a

本文标签： 有向图的欧拉回路