GraphProblem 38 of 43
Paths to travel each nodes using each edge (Seven Bridges)
Problem Statement
Given a graph, determine if there exists a path that visits every edge exactly once (Eulerian path or circuit). This is the famous Seven Bridges of Königsberg problem. If such a path exists, find it.
An Eulerian Circuit visits every edge exactly once and returns to the starting vertex. An Eulerian Path visits every edge exactly once but may start and end at different vertices.
Example:
- Input:
V = 5, edges = [(0,1),(0,2),(1,2),(2,3),(3,4),(2,4)] - Output:
Eulerian Path exists(e.g., 0 → 1 → 2 → 3 → 4 → 2 → 0)
Noob-Friendly Explanation
Imagine you're in a city with bridges. You want to take a walk that crosses every bridge exactly once. Can you do it? This is what mathematician Euler asked about Königsberg's 7 bridges!
The rule is simple:
- If every vertex has an even number of edges (even degree), you can walk in a circuit (start and end at the same place).
- If exactly two vertices have odd degree, you can walk a path (start at one odd vertex, end at the other).
- Otherwise, it's impossible!
Approach 1: Brute Force
Intuition
Try all possible orderings of edges. For each ordering, check if the edges form a valid path (each edge connects to the next). This is extremely slow but conceptually simple.
Algorithm
- Generate all permutations of edges.
- For each permutation, check if consecutive edges share a vertex.
- If a valid sequence is found, an Eulerian path/circuit exists.
java
import java.util.*;
public class EulerianBrute {
static boolean found = false;
static List<int[]> result;
public static void findEulerianPath(int V, int[][] edges) {
int E = edges.length;
found = false;
result = new ArrayList<>();
boolean[] used = new boolean[E];
for (int i = 0; i < E && !found; i++) {
// Try starting with edge i, starting from edges[i][0]
used[i] = true;
List<int[]> path = new ArrayList<>();
path.add(edges[i]);
tryNext(edges, used, path, edges[i][1], E);
if (!found) {
// Try starting from edges[i][1]
path.clear();
path.add(new int[]{edges[i][1], edges[i][0]});
tryNext(edges, used, path, edges[i][0], E);
}
used[i] = false;
}
if (found) {
System.out.println("Eulerian path found!");
} else {
System.out.println("No Eulerian path exists.");
}
}
static void tryNext(int[][] edges, boolean[] used, List<int[]> path, int lastNode, int E) {
if (found) return;
if (path.size() == E) {
found = true;
result = new ArrayList<>(path);
return;
}
for (int i = 0; i < E; i++) {
if (used[i]) continue;
if (edges[i][0] == lastNode || edges[i][1] == lastNode) {
used[i] = true;
int nextNode = edges[i][0] == lastNode ? edges[i][1] : edges[i][0];
path.add(edges[i]);
tryNext(edges, used, path, nextNode, E);
path.remove(path.size() - 1);
used[i] = false;
}
}
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1},{0,2},{1,2},{2,3},{3,4},{2,4}};
findEulerianPath(V, edges);
}
}Complexity Analysis
- Time Complexity: O(E! * E) - trying all permutations of edges
- Space Complexity: O(E) - for the used array and path
Approach 2: Optimal (Hierholzer's Algorithm + Degree Check)
Intuition
First check if an Eulerian path/circuit is possible using degree conditions. Then use Hierholzer's algorithm to find the actual path in linear time. Hierholzer's algorithm follows edges greedily and backtracks to stitch together sub-circuits.
Algorithm
- Count the degree of each vertex.
- If all vertices have even degree → Eulerian Circuit exists.
- If exactly 2 vertices have odd degree → Eulerian Path exists (start from an odd-degree vertex).
- Otherwise → no Eulerian path/circuit.
- Use Hierholzer's algorithm with a stack to find the path.
java
import java.util.*;
public class EulerianOptimal {
public static void findEulerianPath(int V, int[][] edges) {
List<List<int[]>> adj = new ArrayList<>();
for (int i = 0; i < V; i++) adj.add(new ArrayList<>());
int[] degree = new int[V];
for (int idx = 0; idx < edges.length; idx++) {
int u = edges[idx][0], v = edges[idx][1];
adj.get(u).add(new int[]{v, idx});
adj.get(v).add(new int[]{u, idx});
degree[u]++;
degree[v]++;
}
// Check Eulerian conditions
int oddCount = 0;
int startNode = 0;
for (int i = 0; i < V; i++) {
if (degree[i] % 2 != 0) {
oddCount++;
startNode = i;
}
}
if (oddCount != 0 && oddCount != 2) {
System.out.println("No Eulerian path or circuit exists.");
return;
}
if (oddCount == 0) {
System.out.println("Eulerian Circuit exists.");
} else {
System.out.println("Eulerian Path exists.");
}
// Hierholzer's Algorithm
boolean[] usedEdge = new boolean[edges.length];
int[] ptr = new int[V]; // pointer for adjacency list
Stack<Integer> stack = new Stack<>();
List<Integer> path = new ArrayList<>();
stack.push(startNode);
while (!stack.isEmpty()) {
int u = stack.peek();
boolean foundEdge = false;
while (ptr[u] < adj.get(u).size()) {
int[] edge = adj.get(u).get(ptr[u]);
ptr[u]++;
if (!usedEdge[edge[1]]) {
usedEdge[edge[1]] = true;
stack.push(edge[0]);
foundEdge = true;
break;
}
}
if (!foundEdge) {
path.add(stack.pop());
}
}
Collections.reverse(path);
System.out.println("Path: " + path);
}
public static void main(String[] args) {
int V = 5;
int[][] edges = {{0,1},{0,2},{1,2},{2,3},{3,4},{2,4}};
findEulerianPath(V, edges);
}
}Complexity Analysis
- Time Complexity: O(V + E) - Hierholzer's algorithm processes each edge exactly once
- Space Complexity: O(V + E) - for adjacency list, stack, and path