Skip to content

Instantly share code, notes, and snippets.

@neiled

neiled/min_spanning_tree

Created February 7, 2014 16:23
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save neiled/8866195 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save neiled/8866195 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. neiled created this gist Feb 7, 2014.
    46 changes: 46 additions & 0 deletions min_spanning_tree
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,46 @@
    private void connectRooms(List<Room> rooms)
    {
    /*
    Input: A non-empty connected weighted graph with vertices V and edges E (the weights can be negative).
    Initialize: Vnew = {x}, where x is an arbitrary node (starting point) from V, Enew = {}
    Repeat until Vnew = V:
    Choose an edge {u, v} with minimal weight such that u is in Vnew and v is not
    * (if there are multiple edges with the same weight, any of them may be picked)
    Add v to Vnew, and {u, v} to Enew
    Output: Vnew and Enew describe a minimal spanning tree
    */
    var connectedRooms = new List<Room>();
    connectedRooms.Add(rooms.First());

    do
    {
    double minDistance = double.MaxValue;
    Room startRoom = null;
    Room closestRoom = null;
    foreach (var connectedRoom in connectedRooms)
    {
    foreach (var roomToTest in rooms)
    {
    if (connectedRooms.Contains(roomToTest) == false)
    {
    if (closestRoom == null)
    {
    closestRoom = roomToTest;
    minDistance = connectedRoom.DistanceTo(roomToTest);
    startRoom = connectedRoom;
    }
    else if (roomToTest.DistanceTo(connectedRoom) < minDistance)
    {
    closestRoom = roomToTest;
    minDistance = roomToTest.DistanceTo(connectedRoom);
    startRoom = connectedRoom;
    }
    }
    }

    }
    startRoom.Neighbours.Add(closestRoom);
    connectedRooms.Add(closestRoom);

    } while (connectedRooms.Count < rooms.Count);
    }