Euler Circuits in Directed Graphs Using C++
Introduction:
In computer science, graph theory is an intriguing area of research that examines interactions between items. Determining whether a graph has an Euler circuit, and a path that travels across each edge of the graph precisely once before returning to the beginning point is one of the basic issues in graph theory. Although Euler circuits are frequently addressed in relation to undirected graphs, there are further complications when applying them to directed graphs. In this article, we investigate the idea of Euler circuits in directed graphs and examine the C++ implementation of such circuits.
Directed Graphs:
It's important to know directed graphs before learning about Euler circuits. Directed graphs feature edges with a definite direction, as opposed to undirected graphs where edges are randomly oriented. In a directed graph, every edge has a beginning vertex and an ending vertex, suggesting a one-way connection between them.
Euler Circuit in a Directed Graph
A path that begins and finishes at the same vertex and touches each edge precisely once is called an Euler circuit in a directed graph. Certain requirements must be met by a graph in order for it to have an Euler circuit; however, not all directed graphs may have one. This article analyses the existence requirements of Euler circuits in directed graphs and develops a C++ program to identify them.
Criteria for an Euler Circuit in a Graph with Directions
Directed graphs feature two different kinds of degrees, in contrast to undirected graphs, where each vertex's total degree is important.
- In-degree: The quantity of edges pointing in the direction of a vertex.
- Out-degree: The quantity of edges pointing outward from a vertex is called its out-degree.
A directed graph has to satisfy the following requirements in order to have an Euler circuit:
Strongly Connected: There must be strong connections inside the graph. It indicates that a path from u to v and vice versa exists for any two vertices, u and v. Strong connection may be verified via technologies such as Depth-First Search (DFS).
Equivalent In/Out Degrees: Each vertex, with the possible exception of one each for the source and sink, needs to have an equal in-degree and out-degree. The source vertex's out-degree is one degree higher than its in-degree.
Example:
Consider the graph below:
(A) -> (B) -> (C)
| |
v v
(D) <- (E) <- (F)
This graph satisfies the following conditions:
- It has great connectivity, with every vertex accessible from every other.
- The in-degree and out-degree of each vertex (A, B, C, D, and E) are equal (1).
- With an in-degree of two and an out-degree of one, vertex F serves as the sink.
Finding an Euler Circuit: Using Hierholzer's Algorithm for Locating an Euler Circuit
A version of DFS called Hierholzer's method that is used to locate an Euler circuit in a directed graph. It proceeds as follows:
- Check Conditions: It checks to see if the graph maintains the in/out degree balance and is tightly linked. An Euler circuit doesn't exist if it doesn't.
- Start from Source: Locate a vertex where the out-degree is not zero (source). This will be where the DFS traversal begins.
- Recursive DFS: Traverse the graph using DFS, recording the edges we visit.
- Investigate any unexplored outgoing edges at each vertex.
- Go back and investigate an alternative route if there are no unexplored outgoing edges at a vertex.
- Circuit Validity: Verify that every edge has been visited following DFS. The Euler circuit is the path that forms from the initial vertex back to itself if all edges are visited. If not, there is no Euler circuit on the graph.
Example:
Let us take an example to illustrate the Euler Circuits in Directed Graph in C++.
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class DirectedGraph {
int V;
vector<vector<int>> adj;
public:
DirectedGraph(int vertices) : V(vertices) {
adj.resize(V);
}
void addEdge(int u, int v) {
adj[u].push_back(v);
}
void eulerCircuitUtil(int v, vector<bool>& visited, stack<int>& circuit) {
visited[v] = true;
for (int u : adj[v]) {
if (!visited[u]) {
eulerCircuitUtil(u, visited, circuit);
}
}
circuit.push(v);
}
vector<int> findEulerCircuit() {
vector<int> eulerCircuit;
vector<bool> visited(V, false);
stack<int> circuit;
// Check if the graph is strongly connected
for (int i = 0; i < V; ++i) {
if (adj[i].size() > 0) {
eulerCircuitUtil(i, visited, circuit);
break;
}
}
// If the graph is not strongly connected, return empty Euler circuit
for (int i = 0; i < V; ++i) {
if (!visited[i] && adj[i].size() > 0) {
return {};
}
}
// Reconstruct Euler circuit
while (!circuit.empty()) {
eulerCircuit.push_back(circuit.top());
circuit.pop();
}
return eulerCircuit;
}
};
int main() {
DirectedGraph graph(5);
graph.addEdge(0, 1);
graph.addEdge(1, 2);
graph.addEdge(2, 0);
graph.addEdge(2, 3);
graph.addEdge(3, 4);
graph.addEdge(4, 2);
vector<int> eulerCircuit = graph.findEulerCircuit();
if (eulerCircuit.empty()) {
cout << "No Euler circuit exists in the graph." << endl;
} else {
cout << "Euler circuit: ";
for (int vertex : eulerCircuit) {
cout << vertex << " ";
}
cout << endl;
}
return 0;
}
Output:
![Euler Circuits in Directed Graphs Using C++/>
<!-- /wp:html -->
<!-- wp:html -->
<div class=](https://static.tutorialandexample.com/cpp/euler-circuits-in-directed-graphs-using-cpp1.png)