Graph  8. Eulerian Cycle / Eulerian Path
#8. Eulerian Cycle / Eulerian Path
欧拉回路: A Cycle with each
edge
exactly once.
Eulerian Cycle  Eulerian Path  

Undirected Graph  Every vertex has an even degree  Every vertex has an even degree or only 2 vertices can have odd degree 
Directed Graph  Every vertex has the same indegree and outdegree  At most 1 vertex has (outdegree)  (indegree) = 1, and at most 1 vertex has (indegree) (outdegree) = 1, and all other vertices has the same indegree and outdegree 
 If a graph has an Eulerian Cycle, it must have an Eulerian Path
#8.1 Eulerian Cycle for Directed Graph
A directed graph has an Euler Cycle iff:
 Every vertex with nonzero degree belong to a single strongly connected component
 Every vertex must have the same indegree and outdegree
[Notes]
 A singleton is a valid node in the eulerian graph. Because eulerian cycle or eulerian path visit each
edge
once, there is no need to visit that singleton node.  In a directed graph, an eulerian path has only one starting node and only one end node. Starting node has
(outdegree)  (indegree) = 1
, while end node has(indegree)  (outdegree) = 1
Java: Check if the graph has Eulerian Cycle


#8.2 Hierholzer’s Algorithm
Find Euler path/cycle in Directed graph
特别注意这个implementation. 当处理Euler Path/Cycle的问题时，如果需要自己构建graph, 不需要用Inner class来构建Edge, 然后再用类似于Set的数据结构来记录edge的访问情况.
Java Hierholzer’s Algorithm
仔细理解一下下面的code, 用一个Queue来构建adjacency list会省了很多事.


Python Hierholzer’s Algorithm


#8.2 Eulerian Cycle/Path for Undirected Graph
An undirected graph has an Euler Cycle
iff:
 Every vertex with nonzero degree belong to a single connected component
 Every vertex must have
even
number as its degree
Implementation中注意区分Directed Graph里的isStronglyConnected
和Undirected Graph里的isConnected
. Strongly Connected Component的概念只有在Directed Graph里才会出现!


An undirected graph has an Euler Path
iff:
 Every vertex with nonzero degree belong to a single strongly connected component
 Only 0 or 2 vertices are allowed to have
odd
number as its degree, all other vertices must haveeven
number as their degrees.
找path和找cycle几乎一模一样, 唯一的区别就是判断奇数degree的结点个数是不是0或者2

