Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction ⚔️
1.1.
Euler Circuit 💡
1.2.
Problem Statement 🔔
2.
Approach 👀
2.1.
Code Implementation 💻
2.1.1.
Complexity Analysis ⏰ 
3.
Frequently Asked Questions
3.1.
What is an adjacency list?
3.2.
How does Depth First Search works?
3.3.
How is an Euler path different from an Euler circuit?
3.4.
What is a connected component?
4.
Conclusion
Last Updated: Mar 27, 2024
Hard

Minimum Edges Required to Make Euler Circuit

Author Manish Kumar
1 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction ⚔️

Hey Ninja!! 🥷You must have used google maps to find the best way to reach your destination. The underlying algorithm heavily depends on graph traversal techniques and uses a logic similar to the one we will explore. 

Minimum Edges Required to Make Euler Circuit

In this article, we will learn about the Euler circuit and how to complete it if it is not in its correct state. Grab a cup of coffee, and let us jump right into the details of this advanced graph concept!! ☕
 

Euler Circuit

Euler Circuit 💡

An Euler circuit is an Euler path formed when all the graph nodes have even degrees. i.e. if we consider one edge to enter into the node, there should exist a way to exit it.

In other words, it is an eulerian circuit if you can visit all the nodes without lifting the pen from the paper and all nodes are covered. The image below is an example of an Euler circuit.
 

Euler Circuit

Problem Statement 🔔

Given a graph with V vertices and M edges, your task is to find the minimum number of edges required to make the graph an Euler circuit.

For example, look at the graph below:

 

Problem Input


The graph contains all even degree nodes except the node with value '3', so if we connect node 1 with 3, we can form an Euler circuit. Hence the answer here would be 1

Approach 👀

Approach

Let us go through the steps needed to find the number of required edges:

Case 1: The graph contains only one connected component.

  • If there is no node with an odd degree, then we don't need to do anything because the graph is already in eulerian form.
  • If odd-degree edges are there, randomly select pair of nodes and add an edge between them. It can be easily proved that an even number of odd-degree nodes will exist.

Case 2: There is more than one component in the graph.

  • First of all, find if the component is even or odd.
  • Take all the even components and add edges between them. Since a node will be connected to two other nodes, the degree will remain even.
  • After connecting all even components, it becomes an odd component.
  • Circularly connect all odd components to obtain an Euler circuit.

Steps:

  • Create a graph in the form of an adjacency list.
  • Add edges and call the minEdges function.
  • Calculate degrees and call the DFS Algorithm function for each component.
  • Count the number of odd and even components.
  • Calculate the answer based on the number of odd and even components.

Code Implementation 💻

Image

In this section, we will walk through the code implementation in C++. Proper comments are added for ease of understanding:
 

// Coding Ninjas: Graph
#include<bits/stdc++.h>
using namespace std;


//function to add edges to graph
void addEdge(int a,int b,vector<vector<int>>&graph){
    graph[a].push_back(b);
    graph[b].push_back(a);
}


//DFS to find connected components
void DFS(vector<vector<int>>&graph,vector<bool>&visited,vector<int>&oddNodes,vector<int>&degree,int componentID,int V){
    visited[V]=true;
    //checking if the degree of a node is even or odd
    if(degree[V]%2!=0){
        oddNodes[componentID]++;    
    }
    
    for(auto p:graph[V]){
        if(!visited[p]){
            DFS(graph,visited,oddNodes,degree,componentID,p);
        }
    }
}


int minEdges(vector<vector<int>>&graph,int V,int E){
    vector<int>degree(V+1,0);
    vector<bool>visited(V+1,false);
    vector<int>oddNodes(V+1,0);
    
    int countEvenComponents=0,countOddComponents=0;
    int ans=0,componentID=0;
    
    //calculating degrees for each vertex
    for(int i=1;i<=V;i++){
        degree[i]=graph[i].size();
    }
    
    //loop to go through each node
    for(int i=1;i<=V;i++){
        if(!visited[i]){
            componentID++;
            DFS(graph,visited,oddNodes,degree,componentID,i);
            if(oddNodes[componentID]==0)
            countEvenComponents++;
            else
            countOddComponents++;
        }
    }
    
    //calculating answer based on the number of even and odd components
    if(countOddComponents==0&&countEvenComponents==1)
    return 0;
    else if(countOddComponents==0)
    return countEvenComponents;
    else if(countEvenComponents!=0)
    ans+=countEvenComponents;
 
    for(auto p:oddNodes){
        if(p!=0){
            ans+=p/2;
        }
    }
    return ans;
}
int main() {
    int Vertices=5;
    int Edges=5;
    //graph in the form of adjacency list
    vector<vector<int>>graph(6);
    addEdge(1,2,graph);
    addEdge(3,2,graph);
    addEdge(1,4,graph);
    addEdge(1,5,graph);
    addEdge(5,4,graph);
    cout<<"The minimum edges added by Ninja to make eulerian circuit: "<<minEdges(graph, Vertices, Edges);
    return 0;
}

 

Output:

Output

 

Complexity Analysis ⏰
 

Time Complexity: O(V+E),  where V and E are the numbers of vertices and edges, respectively. Time taken by this algorithm if the graph is represented using adjacency matrix representation is the same as DFS traversal.

Space Complexity: O(V+E), where V is the number of vertices and E is the number of edges in the graph. We have to maintain a visited array and list of size V.
 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is an adjacency list?

An adjacency list is a 2-D array of dynamic sizes to represent the graph. It can be built using a vector of arrays or vectors. It is the best way to store graphs.

How does Depth First Search works?

In depth-first search, we tend to enter deeply into one path until no nodes are left to visit. In contrast to the breadth first search, we do not enter all the adjacent nodes of a given node simultaneously.

How is an Euler path different from an Euler circuit?

An Euler path is a path in a graph that visits each node exactly once, while an Euler circuit is an Euler path that starts and ends at the same node.

What is a connected component?

A connected component represents a group of nodes that can be visited, starting from any node to any other node belonging to the same connected component. 

Conclusion

In this blog, we learned how to find the number of edges required to make an Euler circuit in a graph. We went through the algorithm and implemented the code. We also analysed the time and space complexities of our code. We hope you enjoyed reading our blog. To read other graph-related topics, refer to these pages star graphnodes within k-distanceminimum edges between two vertices etc.

Refer to our Guided Path on Coding Ninjas Studio to upskill ourselves in Data Structures and AlgorithmsCompetitive ProgrammingJavaScriptSystem DesignMachine learning, and many more! But suppose we have just started our learning process and are looking for questions from tech giants like Amazon, Microsoft, Uber, etc. In that case, we must look at the problemsinterview experiences, and interview bundles for placement preparations.

Nevertheless, we may consider our paid courses to give our career an edge over others!

Do upvote this blog if you find it helpful and engaging!

Happy Learning!!

Previous article
Minimize the Number of Weakly Connected Nodes
Next article
Biconnected Components in Graph
Live masterclass