Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
min spanning tree
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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment