CODEWITHSUNDEEP
algorithmgraph-theory
Epitheoritis 32
Epitheoritis 32

Reputation: 366

Edge properties in a graph

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 ->edge(1,2),weight=1

1 3 1

2 3 1

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 a MST and then for each edge belonging in G check in(linear?) time if it can 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?

Upvotes: 3

Views: 298

Answers (1)

Yola
Yola

Reputation: 19033

I think it's crucial to notice that every MST have the same set of edges weights. Armed with this knowledge:

  1. Build a MST with some algorithm.
  2. For every edge in MST create the cut which splits MST into two parts.
  3. Check if there other edges with the same weight in the cut
    • if there are, then every of these edges belongs to some MST,
    • if there aren't, the this edge belong to unique MST.
  4. All other edges don't belong to any MST.

We can transform it into the following algorithm. Go with Prim's algorithm, only on every step not just add an edge with the smallest weight, but mark all edges with this weight either as edges of type II if there are more than one such edge or with type I if there is only one such edge. All unmarked edges are of type III.

I - belongs to all, II - belongs to at least one, III - doesn't belong to any.

Upvotes: 1

Related Questions