{"id":1654,"date":"2021-12-18T11:47:34","date_gmt":"2021-12-18T19:47:34","guid":{"rendered":"https:\/\/fighternan.com\/?p=1654"},"modified":"2021-12-18T11:47:34","modified_gmt":"2021-12-18T19:47:34","slug":"eulerian-path-2","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2021\/12\/18\/eulerian-path-2\/","title":{"rendered":"Eulerian Path"},"content":{"rendered":"\n<p>In\u00a0graph theory, an\u00a0<strong>Eulerian trail<\/strong>\u00a0(or\u00a0<strong>Eulerian path<\/strong>) is a\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Trail_(graph_theory)\">trail<\/a>\u00a0in a finite graph that visits every\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Edge_(graph_theory)\">edge<\/a>\u00a0exactly once (allowing for revisiting vertices). Similarly, an\u00a0<strong>Eulerian circuit<\/strong>\u00a0or\u00a0<strong>Eulerian cycle<\/strong>\u00a0is an Eulerian trail that starts and ends on the same\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Vertex_(graph_theory)\">vertex<\/a>.<\/p>\n\n\n\n<p>We have the following properties for undirected graph,<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>An undirected graph has an <strong>Eulerian cycle<\/strong> if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Connected_component_(graph_theory)\">connected component<\/a>.<\/li><li>An undirected graph can be decomposed into edge-disjoint\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Cycle_(graph_theory)\">cycles<\/a>\u00a0if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component.<\/li><li>An undirected graph has an <strong>Eulerian trail<\/strong> if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component<\/li><\/ul>\n\n\n\n<p><meta charset=\"utf-8\">We have the following properties for directed graph,<\/p>\n\n\n\n<ul class=\"wp-block-list\" id=\"block-12923e76-e8f1-4d63-a7aa-90430eb5fcd3\"><li>A directed graph has an <strong>Eulerian cycle<\/strong> if and only if every vertex has equal\u00a0in degree\u00a0and\u00a0out degree, and all of its vertices with nonzero degree belong to a single\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Strongly_connected_component\">strongly connected component<\/a>. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint\u00a0<a href=\"https:\/\/en.wikipedia.org\/wiki\/Cycle_(graph_theory)\">directed cycles<\/a>\u00a0and all of its vertices with nonzero degree belong to a single strongly connected component.<\/li><li>A directed graph has an <strong>Eulerian trail<\/strong> if and only if at most one vertex has\u00a0(<a href=\"https:\/\/en.wikipedia.org\/wiki\/Out_degree_(graph_theory)\">out-degree<\/a>) \u2212 (<a href=\"https:\/\/en.wikipedia.org\/wiki\/In_degree_(graph_theory)\">in-degree<\/a>) = 1,\u00a0at most one vertex has\u00a0(in-degree) \u2212 (out-degree) = 1,\u00a0every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\">Hierholzer&#8217;s algorithm<\/h2>\n\n\n\n<ul class=\"wp-block-list\"><li>Choose any starting vertex&nbsp;<em>v<\/em>, and follow a trail of edges from that vertex until returning to&nbsp;<em>v<\/em>. It is not possible to get stuck at any vertex other than&nbsp;<em>v<\/em>, because the even degree of all vertices ensures that, when the trail enters another vertex&nbsp;<em>w<\/em>&nbsp;there must be an unused edge leaving&nbsp;<em>w<\/em>. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph.<\/li><li>As long as there exists a vertex&nbsp;<em>u<\/em>&nbsp;that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from&nbsp;<em>u<\/em>, following unused edges until returning to&nbsp;<em>u<\/em>, and join the tour formed in this way to the previous tour.<\/li><li>Since we assume the original graph is&nbsp;<a href=\"https:\/\/en.wikipedia.org\/wiki\/Connected_graph\">connected<\/a>, repeating the previous step will exhaust all edges of the graph.<\/li><\/ul>\n\n\n\n<p>By using a data structure such as a\u00a0doubly linked list\u00a0to maintain the set of unused edges incident to each vertex, to maintain the list of vertices on the current tour that have unused edges, and to maintain the tour itself, the individual operations of the algorithm (finding unused edges exiting each vertex, finding a new starting vertex for a tour, and connecting two tours that share a vertex) may be performed in constant time each, so the overall algorithm takes\u00a0linear time,\u00a0{\\displaystyle O(|E|)}<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/976fe7f1e011d0dcdb3d6163754c877aaad5187f\" alt=\"O(|E|)\">.<sup><a href=\"https:\/\/en.wikipedia.org\/wiki\/Eulerian_path#cite_note-9\">[9]<\/a><\/sup><\/p>\n\n\n\n<p>This algorithm may also be implemented with a\u00a0deque. Because it is only possible to get stuck when the deque represents a closed tour, one should rotate the deque by removing edges from the tail and adding them to the head until unstuck, and then continue until all edges are accounted for. This also takes linear time, as the number of rotations performed is never larger than\u00a0{\\displaystyle |E|}<img decoding=\"async\" src=\"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d8c2b9637808cf805d411190b4ae017dbd4ef8d8\" alt=\"|E|\">\u00a0(intuitively, any &#8220;bad&#8221; edges are moved to the head, while fresh edges are added to the tail)<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code lang=\"cpp\" class=\"language-cpp\">\/\/ need to remove arbitary edges once visited, thus we use double linked list\nunordered_map&lt;int, list&lt;int>> node_to_nexts;\n\n\/\/ https:\/\/en.wikipedia.org\/wiki\/Eulerian_path#Hierholzer's_algorithm\n\/\/ at most 2 points that indegree is not equal to outdegree \nunordered_map&lt;int, int> indegree;\nunordered_map&lt;int, int> outdegree;\nunordered_set&lt;int> nodes;\n\ndeque&lt;int> eulerian_path;\n\n\nvoid Dfs(int curr) {\n  while (!node_to_nexts[curr].empty()) {\n    int next = *node_to_nexts[curr].begin();\n    node_to_nexts[curr].erase(node_to_nexts[curr].begin());\n    Dfs(next);\n  }\n  eulerian_path.push_front(curr);\n}\n\nvector&lt;vector&lt;int>> validArrangement(vector&lt;vector&lt;int>>&amp; pairs) {\n\n  for (auto const&amp; p : pairs) {\n    node_to_nexts[p[0]].insert(node_to_nexts[p[0]].end(), p[1]);\n    indegree[p[1]]++;\n    outdegree[p[0]]++;\n    nodes.insert(p[0]);\n    nodes.insert(p[1]);\n  }\n\n  \/\/ if there's a cycle, start can be any point\n  int start = pairs[0][0];\n  for (auto const&amp; node : nodes) {\n    if (int out = outdegree[node], in = indegree[node]; in != out) {\n      if (in &lt; out) {\n        assert(out - in == 1);\n        start = node;\n      }\n    }\n  }\n\n  Dfs(start);\n}<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\">Reference<\/h2>\n\n\n\n<p><a href=\"https:\/\/en.wikipedia.org\/wiki\/Eulerian_path#Hierholzer's_algorithm\">https:\/\/en.wikipedia.org\/wiki\/Eulerian_path#Hierholzer&#8217;s_algorithm<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"<p>In\u00a0graph theory, an\u00a0Eulerian trail\u00a0(or\u00a0Eulerian path) is a\u00a0trail\u00a0in a finite graph that visits every\u00a0edge\u00a0exactly once (allowing for revisiting vertices). Similarly, an\u00a0Eulerian circuit\u00a0or\u00a0Eulerian cycle\u00a0is an Eulerian trail that starts and ends on the same\u00a0vertex. We have the following properties for undirected graph, An undirected graph has an Eulerian cycle if and only if every vertex has even&#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-1654","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\/1654","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=1654"}],"version-history":[{"count":1,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1654\/revisions"}],"predecessor-version":[{"id":1655,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1654\/revisions\/1655"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1654"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1654"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1654"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}