[Solved]: How can I compute the average weight of an undirected graph?

Problem Detail: 

Given a weighted, undirected graph $G = (V,E)$, how can I compute the average weight of edges?
It seems an easy problem (divide the total weight to the number of edges!) but I couldn't manage to find the sum of the edge weights since each edge can be counted several times while iterating through the vertices.

Asked By : cagirici

Answered By : Bartosz Przybylski

If $w(i,j)$ is the weight of edge $ij$ then:

$avg = \frac{1}{2|E|}\sum_{i\neq j}w(i,j)$.

Why $2E$ ? Because when traversing vertices you will calculate both edges $ij$ and $ji$. Since it's the same edge, you are adding its weight twice, so you need to remove this redundancy by dividing by 2.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/27574

 Ask a Question

 Download Related Notes/Documents