## #8. Eulerian Cycle / Eulerian Path

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:

1. Every vertex with non-zero degree belong to a single strongly connected component
2. 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`

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:

1. Every vertex with non-zero degree belong to a single connected component
2. 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:

1. Every vertex with non-zero degree belong to a single strongly connected component
2. Only 0 or 2 vertices are allowed to have `odd` number as its degree, all other vertices must have `even` number as their degrees.

`找path和找cycle几乎一模一样, 唯一的区别就是判断奇数degree的结点个数是不是0或者2`