Explore
ProGrad Programs
Placement Prep
TCS Codevita
Live Placement Training
Live Aptitude Training
Live Programming Training
Webinars
About Us

Edit
Reply




Edit

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

Published on 11 Mar 2020

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.


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,sum _{vin V}deg(v)=2|E|,.


  • 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


C++

Output
Input - Enter the connection of nodes in a graph 1 2 y 2 3 y 2 4 y 3 6 y 4 5 y 4 7 y 5 6 y 6 8 y 7 8 n Output - Total number of edges : 9


Recommended Programs





If you have any feedback about this article and want to improve this, please write to enquiry@faceprep.in
Explore 'c plus plus'
Articles Practice Exercises