Program to Calculate the Edge Cover of a Graph

0 0 2 minutes read

Given the number of vertices N of a graph. The task is to determine the Edge cover.
Edge Cover: Minimum number of edges required to cover all vertex is known as Edge Cover.

Examples:

Input : N = 5
Output : 3

Input : N = 4
Output : 2

Example 1: For N = 5 vertices,

Edge Cover is: 3 (Choosing the edges marked in Red, all of the vertices will get covered)

Example 2: For N = 8 vertices,

Edge Cover is: 4 (Choosing the edges marked in Red, all of the vertices will get covered)

Formula:

Edge Cover = ceil (no. of vertices / 2)

Implementation:

C++

// C++ program to find Edge Cover
#include <bits/stdc++.h>
using namespace std;
 
// Function that calculates Edge Cover
int edgeCover(int n)
{
    float result = 0;
 
    result = ceil(n / 2.0);
 
    return result;
}
 
// Driver Code
int main()
{
    int n = 5;
 
    cout << edgeCover(n);
 
    return 0;
}

Java

// Java program to find Edge Cover
import java.util.*;
import java.lang.*;
import java.io.*;
 
class GFG{
// Function that calculates Edge Cover
static int edgeCover(int n)
{
    int result = 0;
  
    result = (int)Math.ceil((double)n / 2.0);
  
    return result;
}
  
// Driver Code
public static void main(String args[])
{
    int n = 5;
  
    System.out.print(edgeCover(n));
}
 
}

Python3

# Python 3 implementation of the above approach.
 
import math
 
# Function that calculates Edge Cover 
def edgeCover(n):
     
    result = 0
     
    result = math.ceil(n / 2.0)
     
    return result
     
# Driver code      
if __name__ == "__main__" : 
   
    n =  5
   
    print(int(edgeCover(n)))
 
# this code is contributed by Naman_Garg

C#

// C# program to find Edge Cover
using System;
 
class GFG
{
// Function that calculates Edge Cover
static int edgeCover(int n)
{
    int result = 0;
 
    result = (int)Math.Ceiling((double)n / 2.0);
 
    return result;
}
 
// Driver Code
static public void Main ()
{
    int n = 5;
     
    Console.Write(edgeCover(n));
}
}
 
// This code is contributed by Raj

PHP

<?php
// PHP program to find Edge Cover
 
// Function that calculates
// Edge Cover
function edgeCover($n)
{
    $result = 0;
 
    $result = ceil($n / 2.0);
 
    return $result;
}
 
// Driver Code
$n = 5;
 
echo edgeCover($n);
 
// This code is contributed by Raj
?>

Javascript

<script>
 
// javascript program to find Edge Cover
 
// Function that calculates Edge Cover
    function edgeCover(n) {
        var result = 0;
 
        result = parseInt( Math.ceil(n / 2.0));
 
        return result;
    }
 
    // Driver Code
     
        var n = 5;
 
        document.write(edgeCover(n));
 
// This code contributed by gauravrajput1
 
</script>

Output

Time Complexity: O(1), As we are doing constant time operations only.
Auxiliary Space: O(1)

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!