Dada una representación de lista de adyacencia gráfica no dirigida. Escribe una función para contar el número de aristas en el gráfico no dirigido.
Complejidad de tiempo esperada : O(V)
Ejemplos:
Input : Adjacency list representation of
below graph.
Output : 9
La idea se basa en Handshaking Lemma. El lema del apretón de manos se trata de gráficos no dirigidos. En todo grafo no dirigido finito el número de vértices de grado impar es siempre par. El lema del apretón de manos es una consecuencia de la fórmula de suma de grados (a veces también llamado lema del apretón de manos)
Así que recorremos todos los vértices, calculamos la suma de los tamaños de sus listas de adyacencia y finalmente devolvemos sum/2. Debajo de la implementación de la idea anterior
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 shown 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;
}
Java
// Java program to count number of edge in
// undirected graph
import java.io.*;
import java.util.*;
// Adjacency list representation of graph
class Graph
{
int V;
Vector<Integer>[] adj;
//@SuppressWarnings("unchecked")
Graph(int V)
{
this.V = V;
this.adj = new Vector[V];
for (int i = 0; i < V; i++)
adj[i] = new Vector<Integer>();
}
// add edge to graph
void addEdge(int u, int v)
{
adj[u].add(v);
adj[v].add(u);
}
// Returns count of edge in undirected graph
int 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;
}
}
class GFG
{
// Driver Code
public static void main(String[] args) throws IOException
{
int V = 9;
Graph g = new Graph(V);
// making above shown 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);
System.out.println(g.countEdges());
}
}
// This code is contributed by
// sanjeev2552
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 shown 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
C#
// C# program to count number of edge in
// undirected graph
using System;
using System.Collections.Generic;
// Adjacency list representation of graph
class Graph
{
public int V;
public List<int>[] adj;
public Graph(int V)
{
this.V = V;
this.adj = new List<int>[V];
for (int i = 0; i < V; i++)
adj[i] = new List<int>();
}
// add edge to graph
public void addEdge(int u, int v)
{
adj[u].Add(v);
adj[v].Add(u);
}
// Returns count of edge in undirected graph
public int 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].Count;
// The count of edge is always even because in
// undirected graph every edge is connected
// twice between two vertices
return sum / 2;
}
}
class GFG
{
// Driver Code
public static void Main(String[] args)
{
int V = 9;
Graph g = new Graph(V);
// making above shown 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);
Console.WriteLine(g.countEdges());
}
}
// This code is contributed by PrinciRaj1992
Producción:
14
Complejidad del Tiempo: O(V)
Este artículo es una contribución de Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA