{"id":1380,"date":"2020-06-28T16:02:38","date_gmt":"2020-06-28T23:02:38","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1380"},"modified":"2020-06-29T22:11:03","modified_gmt":"2020-06-30T05:11:03","slug":"eulerian-path","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/06\/28\/eulerian-path\/","title":{"rendered":"Eulerian Path"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Summary<\/h2>\n\n\n\n<p>An&nbsp;<strong>Eulerian path<\/strong> is a path&nbsp;in a finite graph that visits every edge&nbsp;exactly once (allowing for revisiting vertices). <\/p>\n\n\n\n<p>An&nbsp;<strong>Eulerian cycle<\/strong> is a Eulerian path that starts and ends on the same&nbsp;vertex.<\/p>\n\n\n\n<p>We give the following properties without proof.<\/p>\n\n\n\n<p>An undirected graph has an Eulerian trail iif <\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>exactly 0 or 2 vertices have odd degree, <\/li><li>its vertices with nonzero degree belong to a single connected component<\/li><\/ol>\n\n\n\n<p>A directed graph has an Eulerian trail iif <\/p>\n\n\n\n<ol class=\"wp-block-list\"><li>at most 1 vertex has (out-degree)&nbsp;\u2212&nbsp;(in-degree)&nbsp;=&nbsp;1<\/li><li>at most one vertex has (in-degree)&nbsp;\u2212&nbsp;(out-degree)&nbsp;=&nbsp;1<\/li><li>every other vertex has equal in-degree and out-degree<\/li><li>all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.<\/li><\/ol>\n\n\n\n<h3 class=\"wp-block-heading\">Hierholzer algorithm<\/h3>\n\n\n\n<p>There is an efficient algorithm to finding Euler cycles or paths: the Hierholzer algorithm.<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Step 1). Starting from any vertex, we keep following the unused edges until we get&nbsp;stuck&nbsp;at certain vertex where we have no more unvisited outgoing edges.<\/li><li>Step 2). We then backtrack to the nearest neighbor vertex in the current path that has unused edges and we&nbsp;repeat&nbsp;the process until all the edges have been used.<\/li><\/ul>\n\n\n\n<p>The first vertex that we got stuck at would be the&nbsp;end point&nbsp;of our&nbsp;Eulerian path. So if we follow all the stuck&nbsp;<em>points<\/em>&nbsp;backwards, we could reconstruct the Eulerian path at the end.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Alphabetical Smallest Eulerian Path<\/h3>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">class AlphabeticalSmallestEulerianPath {\npublic:\n    unordered_map&lt;string, multiset&lt;string>> m;\n    \n    list&lt;string> l;\n    vector&lt;string> findItinerary(vector&lt;vector&lt;string>>&amp; edges) {\n        for (auto const &amp;e : edges) {\n            m[e[0]].insert(e[1]);\n        }\n        string start = kFixedStartPoint;\n        dfs(start);\n        return vector&lt;string>(l.begin(), l.end());\n    }\n    \n    void dfs(string const &amp;curr) {\n        while (m.count(curr)) {\n            string next = *m[curr].begin();\n            m[curr].erase(m[curr].begin());\n            if (m[curr].size() == 0) {\n                m.erase(curr);\n            }\n            dfs(next);\n        }\n        \/\/ Only after all outgoing edges of curr are visited, we return back to the last level \n        l.push_front(curr);\n    }\n};<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"> Reference<\/h2>\n\n\n\n<ol class=\"wp-block-list\"><li><a href=\"https:\/\/oi-wiki.org\/graph\/euler\/\">OI-Wiki\/Euler<\/a><\/li><li><a href=\"https:\/\/en.wikipedia.org\/wiki\/Eulerian_path\">Wikipedia\/Eulerian Path<\/a><\/li><\/ol>\n\n\n\n<p> <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Summary An&nbsp;Eulerian path is a path&nbsp;in a finite graph that visits every edge&nbsp;exactly once (allowing for revisiting vertices). An&nbsp;Eulerian cycle is a Eulerian path that starts and ends on the same&nbsp;vertex. We give the following properties without proof. An undirected graph has an Eulerian trail iif exactly 0 or 2 vertices have odd degree, its&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,66],"tags":[],"class_list":["post-1380","post","type-post","status-publish","format-standard","hentry","category-alg","category-graph-alg"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1380","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1380"}],"version-history":[{"count":5,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1380\/revisions"}],"predecessor-version":[{"id":1405,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1380\/revisions\/1405"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1380"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1380"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1380"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}