graphgraph-theorytheoryminimum-spanning-treekruskals-algorithm

Given an edge, find a minimum spanning tree if exist

I have a weighted undirected graph G and an edge e. I need to find a minimum spanning tree containing e, if and only if it exists.

Solution

  • I can interpret your question 2 different ways:

    1. find all minimum spanning trees. If any contains e, return it. Otherwise return null.
    2. Use Kruskals algorithm, add e to the spanning tree before doing anything else. Build the remaining tree. If you are able to create a minimum spanning return it.

    There are two potential points of failure:

    A. the graph contains components not connected by an edge (no spanning tree exists)
    B. the minimal spanning tree does not contain e

    Approach (1) fails on condition A and B. Approach (2) fails only under condition A.