How to calculate the sum of edge weights of each connected component of a multigraph?

help
#1

You are given the edge list along with their weights. The graph is not necessarily connected and it is undirected. We need to find the summation of edge weight of each connected component of this multigraph.

Using dfs we can identify each of the connected components but as it is a multigraph, I don’t know how to calculate the sum of edge weight.

I think DSU with a “pair<int,int> parent” array so that parent[i].first == root of the component including ith node and parent[i].second == total edge weight upto now might work. We just loop through the edge list and create a connection between two nodes where there exists an edge and add the edge weight to the current parent of this component.
Please enlighten me if DFS can do it for me?

#2

Can’t we take sum of all edges, Like if there are 3 edges connecting A to B, then instead of taking 3 edges take one edge equal to the weight of three. It’s unclear from your question that whether you want to minimize it or not.

#3

No i don’t want to minimize it. I think it’s not only about A and B having multiple edges instead of one. let’s say you have A - B, B - C and C - A. Normal dfs starting from A will count A - B, then goes to B, counts B-C and then goes to C, but C-A will not be counted as A is already visited. If you try to do - take the weight of C-A whether or not A is visited; and call dfs(A) only if A is not visited, then you run into overcounting. Because when you get back to dfs(A), you will encounter A - C, this edge you already took as C - A.

#4

I think you are looking for minimum spanning tree.

#5

I am not. I know what MST is. To simply put : Given a weighted graph simply find out the sum of all of the edge weight. The only thing is the graph might have cycles, multiple edges connecting same set of vertices, simply put its an “undirected multigraph without self loops”. I have already done it with DSU. But I want to know if DFS can do it for me and how.

#6

Unless I completely misunderstand the problem, a simple dfs does it? You seem to be overcomplicating it.

Assuming the graph is stored as adjacency list, with each edge represented by a pair of integers, the first being one of the vertices and the other being the edge weight.

Code 
int n; // number of vertices in the graph
int cmp = 0; // number of connected components
vector<pair<int, int>> g[N]; // this is our graph
int64_t ans[N]; // store the answer here
bool vis[N];

void dfs(int u) {
  vis[u] = true;
  for (auto e : g[u]) {
    int v = e.first, w = e.second;
    ans[cmp] += w; // for each edge you encounter add to sum, irrespective of if you have already visited the vertex before
    if (!vis[v]) dfs(v); // continue with dfs only if it has not already been visited
  }
}

void do_stuff() {
  for (int u = 0; u < n; ++u) {
    if (vis[u]) continue;
    dfs(u);
    ans[cmp] /= 2; // each edge is encountered twice, once from each endpoint
    ++cmp;
  }
}
1 Like
#7

Seems like I actually was over-complicating things. That each edge is always encountered exactly twice, for some reason I looked past it thinking maybe there’s some other problem. Thanks for clearing my doubts.