Program to count the number of edges in an undirected graph | faceprep

Program to count the number of edges in an undirected graph is discussed here. Given an adjacency list representation of an undirected graph, the task is to find the number of edges in it.

count the number of edges in an undirected graph

Algorithm to count the number of edges in an undirected graph

  • Input the adjacency list representation of an undirected graph.
  • In every finite undirected graph, the number of vertices with an odd degree is always even. 
  • Handshaking lemma is a consequence of the degree sum formula, 
  • So we traverse all vertices, compute the sum of sizes of their adjacency lists, and finally return sum/2. 

Program to count the number of edges in an undirected graph is given below.

/* C++ program to count the number of edges in an undirected graph */
#include <bits/stdc++.h>
using namespace std;

/* Graph class declaration with vertex and edges */
class Graph
{
int V ;   // Vertex
list *adj;  // Pointer for the edges
public :
Graph(int V)
{
this->V = V ;
adj = new list[V];  // Add to the list
}
void add_edge_graph(int u, int v) ;  // Function to add edges in a graph
int count_edges_graph() ;  // Function to count the edges
};

/* Function to add edges in a graph */
void Graph :: add_edge_graph(int u, int v)
{
adj[u].push_back(v);
adj[v].push_back(u);
}

/* Function to count the edges */
int Graph :: count_edges_graph()
{
int sum = 0;

for (int i = 0 ; i < V ; i++)
sum += adj[i].size();

/* The count of edge is always even because in undirected graph every edge is connected twice between two vertices */

return sum/2;
}

/* Main Function */

int main()
{
int V = 9 ;
Graph g(V);
int u, v;
char choice;

cout << “\nEnter the connections of the nodes in the graph \n”;
do
{
cin >> u >> v;
cin >> choice;  // Enter the choice, to continue, enter y or Y
g.add_edge_graph(u, v); /* Enter the vertex connection */
}while(choice == ‘y’ || choice == ‘Y’); /* If you want to continue */

cout << “\nTotal number of edges : ” << g.count_edges_graph() << endl;

return 0;
}