Eulerian path and circuit | GeeksforGeeks
Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
通过图（无向图或有向图）中所有边且每边仅通过一次的通路称为欧拉通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。
A graph is called Eulerian if it has an Eulerian Cycle and called Semi-Eulerian if it has an Eulerian Path. The problem seems similar toHamiltonian Path which is NP complete problem for a general graph. Fortunately, we can find whether a given graph has a Eulerian Path or not in polynomial time. In fact, we can find it in O(V+E) time.
Backtracking | Set 6 (Hamiltonian Cycle)
How does this work? ???
In Eulerian path, each time we visit a vertex v, we walk through two unvisited edges with one end point as v. Therefore, all middle vertices in Eulerian Path must have even degree. For Eulerian Cycle, any vertex can be middle vertex, therefore all vertices must have even degree.
https://reeestart.wordpress.com/2016/06/09/graph-euler-cyclepath/
http://www.geeksforgeeks.org/euler-circuit-directed-graph/
Given an array of strings, find if the strings can be chained to form a circle | GeeksforGeeks
Read full article from Eulerian path and circuit | GeeksforGeeks
Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
通过图（无向图或有向图）中所有边且每边仅通过一次的通路称为欧拉通路，相应的回路称为欧拉回路。具有欧拉回路的图称为欧拉图（Euler Graph），具有欧拉通路而无欧拉回路的图称为半欧拉图。
A graph is called Eulerian if it has an Eulerian Cycle and called Semi-Eulerian if it has an Eulerian Path. The problem seems similar toHamiltonian Path which is NP complete problem for a general graph. Fortunately, we can find whether a given graph has a Eulerian Path or not in polynomial time. In fact, we can find it in O(V+E) time.
Backtracking | Set 6 (Hamiltonian Cycle)
Eulerian Cycle
An undirected graph has Eulerian cycle if following two conditions are true.
….a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges).
….b) All vertices have even degree.
An undirected graph has Eulerian cycle if following two conditions are true.
….a) All vertices with non-zero degree are connected. We don’t care about vertices with zero degree because they don’t belong to Eulerian Cycle or Path (we only consider all edges).
….b) All vertices have even degree.
Eulerian Path
An undirected graph has Eulerian Path if following two conditions are true.
….a) Same as condition (a) for Eulerian Cycle
….b) If zero or two vertices have odd degree and all other vertices have even degree. Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)
A graph with no edges is considered Eulerian because there are no edges to traverse.An undirected graph has Eulerian Path if following two conditions are true.
….a) Same as condition (a) for Eulerian Cycle
….b) If zero or two vertices have odd degree and all other vertices have even degree. Note that only one vertex with odd degree is not possible in an undirected graph (sum of all degrees is always even in an undirected graph)
How does this work? ???
In Eulerian path, each time we visit a vertex v, we walk through two unvisited edges with one end point as v. Therefore, all middle vertices in Eulerian Path must have even degree. For Eulerian Cycle, any vertex can be middle vertex, therefore all vertices must have even degree.
class Graph{ private int V; // No. of vertices // Array of lists for Adjacency List Representation private LinkedList<Integer> adj[]; // Constructor Graph(int v) { V = v; adj = new LinkedList[v]; for (int i=0; i<v; ++i) adj[i] = new LinkedList(); } //Function to add an edge into the graph void addEdge(int v, int w) { adj[v].add(w);// Add w to v's list. adj[w].add(v); //The graph is undirected } // A function used by DFS void DFSUtil(int v,boolean visited[]) { // Mark the current node as visited visited[v] = true; // Recur for all the vertices adjacent to this vertex Iterator<Integer> i = adj[v].listIterator(); while (i.hasNext()) { int n = i.next(); if (!visited[n]) DFSUtil(n, visited); } } // Method to check if all non-zero degree vertices are // connected. It mainly does DFS traversal starting from boolean isConnected() { // Mark all the vertices as not visited boolean visited[] = new boolean[V]; int i; for (i = 0; i < V; i++) visited[i] = false; // Find a vertex with non-zero degree for (i = 0; i < V; i++) if (adj[i].size() != 0) break; // If there are no edges in the graph, return true if (i == V) return true; // Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); // Check if all non-zero degree vertices are visited for (i = 0; i < V; i++) if (visited[i] == false && adj[i].size() > 0) return false; return true; } /* The function returns one of the following values 0 --> If grpah is not Eulerian 1 --> If graph has an Euler path (Semi-Eulerian) 2 --> If graph has an Euler Circuit (Eulerian) */ int isEulerian() { // Check if all non-zero degree vertices are connected if (isConnected() == false) return 0; // Count vertices with odd degree int odd = 0; for (int i = 0; i < V; i++) if (adj[i].size()%2!=0) odd++; // If count is more than 2, then graph is not Eulerian if (odd > 2) return 0; // If odd count is 2, then semi-eulerian. // If odd count is 0, then eulerian // Note that odd count can never be 1 for undirected graph return (odd==2)? 1 : 2; }void Graph::DFSUtil(int v, bool visited[]){ // Mark the current node as visited and print it visited[v] = true; // Recur for all the vertices adjacent to this vertex list<int>::iterator i; for (i = adj[v].begin(); i != adj[v].end(); ++i) if (!visited[*i]) DFSUtil(*i, visited);}// Method to check if all non-zero degree vertices are connected.// It mainly does DFS traversal starting frombool Graph::isConnected(){ // Mark all the vertices as not visited bool visited[V]; int i; for (i = 0; i < V; i++) visited[i] = false; // Find a vertex with non-zero degree for (i = 0; i < V; i++) if (adj[i].size() != 0) break; // If there are no edges in the graph, return true if (i == V) return true; // Start DFS traversal from a vertex with non-zero degree DFSUtil(i, visited); // Check if all non-zero degree vertices are visited for (i = 0; i < V; i++) if (visited[i] == false && adj[i].size() > 0) return false; return true;}/* The function returns one of the following values 0 --> If grpah is not Eulerian 1 --> If graph has an Euler path (Semi-Eulerian) 2 --> If graph has an Euler Circuit (Eulerian) */int Graph::isEulerian(){ // Check if all non-zero degree vertices are connected if (isConnected() == false) return 0; // Count vertices with odd degree int odd = 0; for (int i = 0; i < V; i++) if (adj[i].size() & 1) odd++; // If count is more than 2, then graph is not Eulerian if (odd > 2) return 0; // If odd count is 2, then semi-eulerian. // If odd count is 0, then eulerian // Note that odd count can never be 1 for undirected graph return (odd)? 1 : 2;}https://reeestart.wordpress.com/2016/06/09/graph-euler-cyclepath/
Euler Cycle is a cycle that visit each EDGE only once. But each vertex could be visited multiple times.
Hamilton Cycle is a cycle that visit each VERTEX only once.
Euler path is a a path in the graph that visits each edge only once.
For example:
1-> 2-> 3-> 4 is an Euler path but not an Euler Cycle.
For example:
1-> 2-> 3-> 4 is an Euler path but not an Euler Cycle.
1-> 2-> 3-> 4-> 1 is an Euler Cycle.
[Directed Graph]
For a directed graph, it 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 in-degree and out-degree.
(See Graph – Strongly Connected Component for more details about SCC)
For a directed graph, it 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 in-degree and out-degree.
(See Graph – Strongly Connected Component for more details about SCC)
[Undirected Graph]
For a undirected graph, it has an Euler Cycle IFF
(1). Every vertex with non-zero degree belong to a single strongly connected component.
(2). Every vertex must have EVEN number of degrees.
For a undirected graph, it has an Euler Cycle IFF
(1). Every vertex with non-zero degree belong to a single strongly connected component.
(2). Every vertex must have EVEN number of degrees.
For a undirected graph, it 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 can have ODD number of degrees, other vertices all have even number of degrees.
(1). Every vertex with non-zero degree belong to a single strongly connected component.
(2). Only 0 or 2 vertices can have ODD number of degrees, other vertices all have even number of degrees.
public class EulerCycle { /* Euler Cycle for Directed Graph */ /* Condition: 1. Every vertex has the same indegree and outdegree 2. All vertices with non-zero degrees belong to a single strongly connected component */ public static boolean hasEulerCycle_Directed(Map<Integer, Set<Integer>> graph) { return isSCC(graph) && hasSameDegree(graph); } private static boolean isSCC(Map<Integer, Set<Integer>> graph) { if (graph == null && graph.isEmpty()) { throw new IllegalArgumentException(); } int[] visited = new int[graph.size()]; dfs(0, visited, graph); for (int tmp : visited) { if (tmp == 0) { return false; } } Arrays.fill(visited, 0); dfs(0, visited, reversed(graph)); for (int tmp : visited) { if (tmp == 0) { return false; } } return true; } private static void dfs(int v, int[] visited, Map<Integer, Set<Integer>> graph) { if (visited[v] == 1) { return; } visited[v] = 1; for (int adj : graph.get(v)) { dfs(adj, visited, graph); } } private static Map<Integer, Set<Integer>> reversed(Map<Integer, Set<Integer>> graph) { Map<Integer, Set<Integer>> reversedGraph = new HashMap<>(); for (int v : graph.keySet()) { for (int adj : graph.get(v)) { reversedGraph.putIfAbsent(adj, new HashSet<>()); reversedGraph.get(adj).add(v); } } return reversedGraph; } private static boolean hasSameDegree(Map<Integer, Set<Integer>> graph) { Map<Integer, Integer> indegree = new HashMap<>(); Map<Integer, Integer> outdegree = new HashMap<>(); for (int v : graph.keySet()) { for (int adj : graph.get(v)) { indegree.put(adj, indegree.getOrDefault(adj, 0) + 1); outdegree.put(v, outdegree.getOrDefault(v, 0) + 1); } } for (int v : indegree.keySet()) { if (!outdegree.containsKey(v) || indegree.get(v) != outdegree.get(v)) { return false; } } return true; } /* Euler Cycle for Undirected Graph */ /* Condition: 1. All vertices with non-zero degree belong to a single strongly connected component 2. All vertices must have even number of degrees */ public static boolean hasEulerCycle_Undirected(Map<Integer, Set<Integer>> graph) { return isSCCUn(graph) && isCycleDegree(graph); } /* Euler Path for Undirected Graph */ /* Condition: 1. All vertices with non-zero degree belong to a single strongly connected component 2. Only 0 or 2 vertices can have odd number of degrees */ public static boolean hasEulerPath_Undirected(Map<Integer, Set<Integer>> graph) { return isSCCUn(graph) && isPathDegree(graph); } private static boolean isSCCUn(Map<Integer, Set<Integer>> graph) { int[] visited = new int[graph.size()]; dfsUn(0, visited, graph); for (int v : visited) { if (v == 0) { return false; } } return true; } private static void dfsUn(int v, int[] visited, Map<Integer, Set<Integer>> graph) { if (visited[v] == 1) { return; } visited[v] = 1; for (int adj : graph.get(v)) { dfsUn(adj, visited, graph); } } /* All even */ private static boolean isCycleDegree(Map<Integer, Set<Integer>> graph) { int[] degree = new int[graph.size()]; for (int v : graph.keySet()) { degree[v] += graph.get(v).size(); for (int adj : graph.get(v)) { degree[adj]++; } } for (int v : degree) { if (v % 2 != 0) { return false; } } return true; } /* Only 0 or 2 odd */ private static boolean isPathDegree(Map<Integer, Set<Integer>> graph) { int[] degree = new int[graph.size()]; for (int v : graph.keySet()) { degree[v] += graph.get(v).size(); for (int adj : graph.get(v)) { degree[adj]++; } } int oddCnt = 0; for (int v : degree) { if (v % 2 != 0) { oddCnt++; } } return oddCnt == 0 || oddCnt == 2; }}http://www.geeksforgeeks.org/euler-circuit-directed-graph/
How to check if a directed graph is eulerian?
A directed graph has an eulerian cycle if following conditions are true
1) All vertices with nonzero degree belong to a single strongly connected component.
2) In degree and out degree of every vertex is same.
A directed graph has an eulerian cycle if following conditions are true
1) All vertices with nonzero degree belong to a single strongly connected component.
2) In degree and out degree of every vertex is same.
We can detect singly connected component using Kosaraju’s DFS based simple algorithm.
To compare in degree and out degree, we need to store in degree an out degree of every vertex. Out degree can be obtained by size of adjacency list. In degree can be stored by creating an array of size equal to number of vertices.
To compare in degree and out degree, we need to store in degree an out degree of every vertex. Out degree can be obtained by size of adjacency list. In degree can be stored by creating an array of size equal to number of vertices.
Time complexity of the above implementation is O(V + E) as Kosaraju’s algorithm takes O(V + E) time. After running Kosaraju’s algorithm we traverse all vertices and compare in degree with out degree which takes O(V) time.
private int V; // No. of vertices private LinkedList<Integer> adj[];//Adjacency List private int in[]; //maintaining in degree //Constructor Graph(int v) { V = v; adj = new LinkedList[v]; in = new int[V]; for (int i=0; i<v; ++i) { adj[i] = new LinkedList(); in[i] = 0; } } //Function to add an edge into the graph void addEdge(int v,int w) { adj[v].add(w); in[w]++; } // A recursive function to print DFS starting from v void DFSUtil(int v,Boolean visited[]) { // Mark the current node as visited visited[v] = true; int n; // Recur for all the vertices adjacent to this vertex Iterator<Integer> i =adj[v].iterator(); while (i.hasNext()) { n = i.next(); if (!visited[n]) DFSUtil(n,visited); } } // Function that returns reverse (or transpose) of this graph Graph getTranspose() { Graph g = new Graph(V); for (int v = 0; v < V; v++) { // Recur for all the vertices adjacent to this vertex Iterator<Integer> i = adj[v].listIterator(); while (i.hasNext()) { g.adj[i.next()].add(v); (g.in[v])++; } } return g; } // The main function that returns true if graph is strongly // connected Boolean isSC() { // Step 1: Mark all the vertices as not visited (For // first DFS) Boolean visited[] = new Boolean[V]; for (int i = 0; i < V; i++) visited[i] = false; // Step 2: Do DFS traversal starting from first vertex. DFSUtil(0, visited); // If DFS traversal doesn't visit all vertices, then return false. for (int i = 0; i < V; i++) if (visited[i] == false) return false; // Step 3: Create a reversed graph Graph gr = getTranspose(); // Step 4: Mark all the vertices as not visited (For second DFS) for (int i = 0; i < V; i++) visited[i] = false; // Step 5: Do DFS for reversed graph starting from first vertex. // Staring Vertex must be same starting point of first DFS gr.DFSUtil(0, visited); // If all vertices are not visited in second DFS, then // return false for (int i = 0; i < V; i++) if (visited[i] == false) return false; return true; } /* This function returns true if the directed graph has an eulerian cycle, otherwise returns false */ Boolean isEulerianCycle() { // Check if all non-zero degree vertices are connected if (isSC() == false) return false; // Check if in degree and out degree of every vertex is same for (int i = 0; i < V; i++) if (adj[i].size() != in[i]) return false; return true; }Given an array of strings, find if the strings can be chained to form a circle | GeeksforGeeks
Read full article from Eulerian path and circuit | GeeksforGeeks
