eulerian path and circuit for undirected graph Algorithm
An Eulerian path is a trail in a finite graph that visits every edge exactly once, allowing for revisiting vertices. In an undirected graph, an Eulerian path exists if and only if the graph is connected and has either zero or exactly two vertices of odd degree. A connected graph is a graph where there is a path between every pair of vertices. Degree, in graph theory, refers to the number of edges incident to a vertex. If a vertex has an odd degree, it means there are an odd number of edges connected to it. Eulerian path algorithms, such as Fleury's Algorithm and Hierholzer's Algorithm, are designed to find these paths efficiently.
An Eulerian circuit, on the other hand, is an Eulerian path that starts and ends at the same vertex, forming a closed loop. For an undirected graph to have an Eulerian circuit, it must be connected and have all vertices of even degree. One of the most famous problems involving Eulerian circuits is the Seven Bridges of Königsberg, which led to the development of graph theory in the 18th century. Eulerian circuit algorithms seek to find efficient ways of traversing these graphs while visiting each edge exactly once, providing valuable insights for various applications, such as route planning and DNA sequence assembly.
# 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.
# time complexity is O(V+E)
# space complexity is O(VE)
# using dfs for finding eulerian path traversal
def dfs(u, graph, visited_edge, path=[]):
path = path + [u]
for v in graph[u]:
if visited_edge[u][v] is False:
visited_edge[u][v], visited_edge[v][u] = True, True
path = dfs(v, graph, visited_edge, path)
return path
# for checking in graph has euler path or circuit
def check_circuit_or_path(graph, max_node):
odd_degree_nodes = 0
odd_node = -1
for i in range(max_node):
if i not in graph.keys():
continue
if len(graph[i]) % 2 == 1:
odd_degree_nodes += 1
odd_node = i
if odd_degree_nodes == 0:
return 1, odd_node
if odd_degree_nodes == 2:
return 2, odd_node
return 3, odd_node
def check_euler(graph, max_node):
visited_edge = [[False for _ in range(max_node + 1)] for _ in range(max_node + 1)]
check, odd_node = check_circuit_or_path(graph, max_node)
if check == 3:
print("graph is not Eulerian")
print("no path")
return
start_node = 1
if check == 2:
start_node = odd_node
print("graph has a Euler path")
if check == 1:
print("graph has a Euler cycle")
path = dfs(start_node, graph, visited_edge)
print(path)
def main():
G1 = {1: [2, 3, 4], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [4]}
G2 = {1: [2, 3, 4, 5], 2: [1, 3], 3: [1, 2], 4: [1, 5], 5: [1, 4]}
G3 = {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2], 4: [1, 2, 5], 5: [4]}
G4 = {1: [2, 3], 2: [1, 3], 3: [1, 2]}
G5 = {
1: [],
2: []
# all degree is zero
}
max_node = 10
check_euler(G1, max_node)
check_euler(G2, max_node)
check_euler(G3, max_node)
check_euler(G4, max_node)
check_euler(G5, max_node)
if __name__ == "__main__":
main()
