To motivate the need to use graphs, we examine the following problem
Heroes in Tamil movies are capable of superhuman feats. For example, they can jump between buildings, jump onto and from running trains, catch bullets with their hands and teeth and so on. A perceptive follower of such movies would have noticed that there are limits to what even the superheroes can do. For example, if the hero could directly jump to his ultimate destination, that would reduce the action sequence to nothing and thus make the movie quite boring. So he typically labours through a series of superhuman steps to reach his ultimate destination.
In this problem, our hero has to save his wife / mother / child / dog /... held captive by the nasty villain on the top floor of a tall building in the centre of Bombay / Bangkok / Kuala Lumpur /.... Our hero is on top of a (different) building. In order to make the action "interesting" the director has decided that the hero can only jump between buildings whose height is within 10 metres.
Given the arrangement of buildings and their heights, your aim is determine whether it is possible for the hero to reach the captive.
Here is an example where the goal is to get from the top left building to the bottom right building.
70 80 80 70 60 30 20 30 50 40 10 50 45 60 20 10
Here is a possible path:
70 80 80 70 | 60 30 -- 20 30 | | | 50 -- 40 10 50 | 45 60 20 -- 10
How do we find such a path? We systematically calculate all the buildings that are reachable. For each building, we know (by the heights) which of the neighbouring buildings can be reached in one step.
Using this procedure, we can grow the set of all reachable buildings until we cannot add any more buildings. At this point, we check if the target building is in the reachable set.
How do we code this? Here is a recursive solution:
check(i,j){ // Assuming that (i,j) has just been marked, n // mark all its neighbours if ((i-1,j) within grid && // Nbr within grid abs(A[i-1][j] - A[i][j] <= 10) && // Difference is OK Mark[i-1][j] == 0){ // Nbr unmarked Mark[i-1][j] = 1; check(i-1,j); } /* Similarly check (i+1,j), (i,j-1), (i,j+1) */ ... }
For each (i,j), check(i,j) is called at most once and processing check(i,j) takes constant time since each building has at most four neighbours, so this will take time proportional to N^{2}, the total number of buildings.
What if, in addition, we want to compute the shortest route from (1,1) to (N,N)?
An efficient way to maintain and process marked positions is to use a queue (first-in-first-out collection).
For instance:
70 80 80 70 60 30 20 30 50 40 10 50 45 60 20 10
Let us examine the order in which positions get marked. When we explore a position that is k steps away from the starting position, its neighbours are k+1 steps away and get added later in the queue. By maintaining the marked positions in the queue, we guarantee that positions are marked in increasing order of their distance from the source. We can also record the distance with each node as we visit it.
This method of exploration, in which we explore all neighbours level by level, is called breadth first search.
The earlier recursive formulation (using "check(i,j)") is depth first search. We pick a neigbhour to explore, then explore its neighbours, … till we can make no progress, and then we come back to process the next unmarked neighbour of the first node.
Here is a more precise formulation of breadth first search:
Mark[(i,j)] = 0 for all (i,j) Mark[(1,1)] = 1; Dist[(1,1)] = 0; Insert (1,1) into the queue; BFS { while (queue is not empty) { v = head of queue; for each unmarked neighbour w of v { Mark[w] = 1; Dist[w] = Dist[v] + 1; Insert w into the queue; } } }
©IARCS 2012–2016
PÄ›stujeme web | visit: Skluzavky