Necessary to MST edges in a graph

0
votes

Given a G(V,E) weighted(on edges) graph i need to find the number of edges that belong in every MST as well as the number of the edges that belong in at least one but not all and the ones that belong in none.

The graph is given as input in the following form(example):

3 3

1 2 1

1 3 1

2 3 2

First 3 is the number of nodes,second 3 is the number of edges.The following three lines are the edges where first number is where they start,second is where they end and third is the value.

I've thought about running kruskal once to find an MST and then for each edge belonging in G check in(linear?) time if it can be replace an edge in this MST without altering it's overall weight.If it can't it belongs in none.If it can it belongs in one but not all.I can also mark the edges in the first MST(maybe with a second value 1 or 0)and in the end check how many of them could not be replaced.These are the ones belonging in every possible MST. This algorithm is probably O(V^2) and i am not quite sure how to write it in C++.My questions are,could we somehow reduce it's complexity? If i add an edge to the MST how can i check(and implement in C++) if the cycle formed contains an edge that has less weight?

1
algorithmgraph
math.stackexchange.com/questions/2577365/… – juvian

1 Answers

0
votes

You can do this by adding some extra work to Kruskal's algorithm.

In Kruskal's algorithm, edges with the same weight can be in any order, and the order in which they are actually checked determines which MST you get out of all possible MSTs. For every MST, there is a sort-consistent order of the edges that will produce that tree.

No matter what sort-consistent order is used, the state of the union-find structure will be the same between weights.

If there is only one edge of a specific weight, then it is in every MST if Kruskal's algorithm selects it, because it would be selected with any sort-consistent edge order, and otherwise it is in no MSTs.

If there are multiple edges with the same weight, and Kruskal's algorithm would select at least one of them, then you can pause Kruskal's at that point and make a new (small) graph with just those edges that connect different sets, using the sets that they connect as vertices.

All of those edges are in at least one MST, because Kruskal's might pick them first. Any of those edges that are bridges in the new graph are in every MST, because Kruskal's would select them no matter what. See: https://en.wikipedia.org/wiki/Bridge_(graph_theory)

So, modify Kruskal's algorithm as follows:

  • When Kruskal's would select an edge, before doing the union, gather and process ALL the non-redundant edges with the same weight.
  • Make a small graph with those edges using the find() sets they connect as vertices
  • Use Tarjan's algorithm or equivalent (see the link) to find all the bridges in the graph. Those edges are in ALL MSTs.
  • The remaining edges in the small graph are in some, but not all, MSTs.
  • perform all the unions for edges in the small graph and move on to the next weight.

Since bridge-finding can be done in linear time, and every edge is in at most one small graph, the whole algorithm is still O(|V| + |E| log |E|).