Question

2.3 We are are interested in examining if it is possible to evacuate the rooms in case of fire. The entrance is a special room on the floor plan. A fire door is a door that will automatically close in case of fire. A room can be evacuated to the entrance if there is a connection from the room to the entrance that does not use any fire doors. Give an algorithm that given a floor plan, an entrance e and a set B of k fire doors determines if all rooms can be evacuated to e. Analyze the running time of your algorithm in the relevant parameters of the problem.

2 Floor Plans Afloor plan consists of a set of R rooms ro., TR-1 and D doors do, .., dn-1 that each connects exactly two rooms. Each room is a geometric figure and a door between two rooms are indicated by three small bold lines between the rooms. For instance, the following floor plan P consists of 11 rooms and 12 doors

Answer 1

So once the graph created from the room and door plan, we are interested to know whether there exist a path from every room to the entrance e without using any fire door.

So answer is very simple. Given the graph G=(V,E) where one of the vertex is e which is entrance, perform following steps:-

1. Remove those edges from the graph G=(V,E) which corresponds to fire door.

2. Now we need to check whether every vertices v in V is connected to vertex e or not when fire door has been removed. In order to check this, perform Breadth First Search in graph G=(V,E) starting from vertex e, which will created BFS tree with root vertex e.

3. If the BFS tree with root e covers all the vertices in G=(V,E) then this means there exist path from every room to the entrance e without any fire door. And if BFS tree does not over all the vertices, then this means every vertices are not connected to entrance e without any fire door.

So the time complexity of above task will be O(V+E) which is the time complexity of performing BFS on graph G=(V,E).

Please comment for any clarification.