Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Example
3.1.
Input
3.2.
Output
3.3.
Explanation
4.
Algorithm
4.1.
C++ Code
4.2.
Java Code
4.3.
Input
4.4.
Output
5.
Complexities
5.1.
Time complexity 
5.2.
Space complexity 
6.
Frequently Asked Questions
6.1.
What memory representation does a graph have?
6.2.
What do you mean by depth of a vertex?
6.3.
What is the load factor of a hash table?
6.4.
What technique is employed to depict a graph in relation?
6.5.
How come Breath-First Search is quicker than DFS? 
7.
Conclusion
Last Updated: Mar 27, 2024
Medium

Count Number of Edges in an Undirected Graph

Author Saksham Gupta
0 upvote

Introduction

Graphs is the most asked topic when it comes to coding interviews. So to help you in your preparation, Ninjas are here to help you. In the article, we will discuss one of the most asked questions, counting the number of edges in an undirected graph.

Introduction

Problem Statement

In this problem, we need to calculate the total number of edges in the graph. In every finite undirected graph number of vertices with odd degrees is always even. Therefore, we walk through every vertex, add up the sizes of their adjacency lists, and then return sum/2.

Example

Input

Input

Output

5

Explanation

We can see that the total number of edges in the above graph is 5, namely 0->10->20->3, 3->4, and 2->1.

Note: We have taken 1->2 and 2->1 as a  single edge only.

Now, let's see the proper algorithm and the implementation of the code.

Algorithm

Handshake lemma is defined for an undirected graph. 

We know that every undirected graph with an even number of vertices has an odd degree. The degree sum formula leads to the handshaking lemma(You can refer to the above article for more details on the handshaking lemma).

Therefore, To find the number of edges:

  1. We will traverse through every vertex
  2.  Add up the sizes of their adjacency lists, and then return sum/2.

 

Now, Let's see the implementation of the code.

Implementation

C++ Code

/*C++ program */
#include <bits/stdc++.h>
using namespace std;

class Graph
{

	/*number of vertices */
	int vertices;

	/*adjacency lists */
	list<int> *adj;

	public:

		Graph(int vertices)
		{
			this->vertices = vertices;
			adj = new list < int>[vertices];
		}

	void addEdgeToGraph(int source, int destination);
	int countEdgesInGraph();

};

/*function adds an edge to a graph */

void Graph::addEdgeToGraph(int source, int destination)
{
	adj[source].push_back(destination);
	adj[destination].push_back(source);
}

/*this function returns total number of edges in an undirected graph */
int Graph::countEdgesInGraph()
{

	int sum = 0;

	/*traversing all the vertex */
	for (int i = 0; i < vertices; i++)
	{
		sum += adj[i].size();
	}

	return sum / 2;

}

/*Main program */
int main()

{

	/*Creating a graph as shown in above figure */
	int vertices = 5;

	Graph graph(vertices);
	graph.addEdgeToGraph(0, 2);
	graph.addEdgeToGraph(0, 3);
	graph.addEdgeToGraph(1, 0);
	graph.addEdgeToGraph(2, 1);
	graph.addEdgeToGraph(3, 4);
	
	cout << graph.countEdgesInGraph() << endl;

	return 0;

}

Java Code

/*Java program */

import java.io.*;

import java.util.*;

class Graph
{

	/*number of vertices */
	int vertices;

	/*adjacency lists */
	Vector < Integer>[] adj;

	Graph(int vertices)
	{
		this.vertices = vertices;
		this.adj = new Vector[vertices];

		for (int i = 0; i < vertices; i++)
		{
			adj[i] = new Vector<Integer> ();
		}
	}

	/*function adds an edge to a graph */
	void addEdgeToGraph(int source, int destination)
	{
		adj[source].add(destination);
		adj[destination].add(source);
	}

	/*this function returns total number of edges in an undirected graph */
	int countEdgesInGraph()
	{
		int sum = 0;
		
		/*traversing all the vertex */
		for (int i = 0; i < vertices; i++)
		{
			sum += adj[i].size();
		}

		return sum / 2;
	}
}

class Main
{
	/*Main program */
	public static void main(String[] args) throws IOException
	{
		/*Creating a graph as shown in above figure */
		int vertices = 5;

		Graph graph = new Graph(vertices);

		graph.addEdgeToGraph(0, 2);
		graph.addEdgeToGraph(0, 3);
		graph.addEdgeToGraph(1, 0);
		graph.addEdgeToGraph(2, 1);
		graph.addEdgeToGraph(3, 4);

		System.out.println(graph.countEdgesInGraph());
	}
}

Input

Input

Output

5

Complexities

Time complexity 

O(V), where V is the vertex in a graph.

Reason: We need to iterate all the v vertices while summing up all the adjacent vertices of a particular vertex. So, the time complexity will be O(V).

Space complexity 

O(V), where V is the vertex in a graph

Reason: The complexity of space is of order N because auxiliary space is utilized when building arrays.

Frequently Asked Questions

What memory representation does a graph have?

A graph can be kept in memory in three ways: Edges act as pointers and nodes as objects. A matrix that includes each edge weight that connects nodes x and y. edges between numbered nodes, listed.

What do you mean by depth of a vertex?

The number of branches that lead from a root to a vertex determines the vertex's depth. Therefore, the root's depth is zero. The number of the vertex in the path from the root to the vertex determines the vertex's level.

What is the load factor of a hash table?

The load factor can be defined as (m/n), where m is the preferred number of entries that can be added before the size of the underlying data structure needs to be increased, and n is the overall size of the hash table.

What technique is employed to depict a graph in relation?

The adjacency matrix is used to achieve this type of representation. The adjacency matrix shows which nodes are close on a graph or whether an edge connects two nodes.

How come Breath-First Search is quicker than DFS? 

Breath-First Search should usually be quicker if the searched element is typically higher in the search tree because it travels level by level and can be stopped when a matched element is discovered. If the searched element is usually rather deep and locating one among many is adequate, DFS might be faster.

Also Read - Strong number in c

Conclusion

In the article, we have discussed one popular question: count the number of edges in an undirected graph. We hope that this article will help you understand the concept of a graph, and if you want to learn more about the graph, check out our other blogs on graphs:

Refer to our guided paths on Coding Ninjas Studio to learn about Data Structure and Algorithms, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to our mock test available. Have a look at the interview experiences and interview bundle for placement preparations.

Happy Coding!

Live masterclass