min spanning tree

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);
        }