Given an adjacency list representation undirected graph. Write a function to count the number of edges in the undirected graph.
Expected time complexity : O(V)
Examples:
Input : Adjacency list representation of
below graph.
Output : 9
Idea is based on Handshaking Lemma. Handshaking lemma is about undirected graph. In every finite undirected graph number of vertices with odd degree is always even. The handshaking lemma is a consequence of the degree sum formula (also sometimes called the handshaking lemma)
So we traverse all vertices, compute sum of sizes of their adjacency lists, and finally returns sum/2. Below implementation of above idea
C++
// C++ program to count number of edge in // undirected graph #include<bits/stdc++.h> using namespace std; // Adjacency list representation of graph class Graph { int V ; list < int > *adj; public : Graph( int V ) { this->V = V ; adj = new list<int>[V]; } void addEdge ( int u, int v ) ; int countEdges () ; }; // add edge to graph void Graph :: addEdge ( int u, int v ) { adj[u].push_back(v); adj[v].push_back(u); } // Returns count of edge in undirected graph int Graph :: countEdges() { int sum = 0; //traverse all vertex for (int i = 0 ; i < V ; i++) // add all edge that are linked to the // current vertex 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; } // driver program to check above function int main() { int V = 9 ; Graph g(V); // making above uhown graph g.addEdge(0, 1 ); g.addEdge(0, 7 ); g.addEdge(1, 2 ); g.addEdge(1, 7 ); g.addEdge(2, 3 ); g.addEdge(2, 8 ); g.addEdge(2, 5 ); g.addEdge(3, 4 ); g.addEdge(3, 5 ); g.addEdge(4, 5 ); g.addEdge(5, 6 ); g.addEdge(6, 7 ); g.addEdge(6, 8 ); g.addEdge(7, 8 ); cout << g.countEdges() << endl; return 0; } |
Python3
# Python3 program to count number of # edge in undirected graph # Adjacency list representation of graph class Graph: def __init__(self, V): self.V = V self.adj = [[] for i in range(V)] # add edge to graph def addEdge (self, u, v ): self.adj[u].append(v) self.adj[v].append(u) # Returns count of edge in undirected graph def countEdges(self): Sum = 0 # traverse all vertex for i in range(self.V): # add all edge that are linked # to the current vertex Sum += len(self.adj[i]) # The count of edge is always even # because in undirected graph every edge # is connected twice between two vertices return Sum // 2 # Driver Code if __name__ == '__main__': V = 9 g = Graph(V) # making above uhown graph g.addEdge(0, 1 ) g.addEdge(0, 7 ) g.addEdge(1, 2 ) g.addEdge(1, 7 ) g.addEdge(2, 3 ) g.addEdge(2, 8 ) g.addEdge(2, 5 ) g.addEdge(3, 4 ) g.addEdge(3, 5 ) g.addEdge(4, 5 ) g.addEdge(5, 6 ) g.addEdge(6, 7 ) g.addEdge(6, 8 ) g.addEdge(7, 8 ) print(g.countEdges()) # This code is contributed by PranchalK |
Output:
14
Time Complexity: O(V)
Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.
leave a comment
0 Comments