{"id":2022,"date":"2020-07-01T09:51:02","date_gmt":"2020-07-01T09:51:02","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2022"},"modified":"2022-03-30T22:57:22","modified_gmt":"2022-03-30T22:57:22","slug":"ragnar-lorthbrok","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/ragnar-lorthbrok\/","title":{"rendered":"Ragnar Lorthbrok"},"content":{"rendered":"

\"\"<\/p>\n

Concepts Used<\/h3>\n
\n

Breadth First Search<\/p>\n<\/blockquote>\n

Difficulty Level<\/h3>\n
\n

Easy<\/p>\n<\/blockquote>\n

Problem Statement :<\/h3>\n
\n

Given locations of X<\/code> & Y<\/code> islands, we need to find the minimum distance between a given pair of islands (X,Y)<\/code>.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

Solution Approach :<\/h3>\n

Introduction :<\/h4>\n
\n

We can calculate distance between any two nodes by counting the number of edges between them. We can perform either Breadth First Search<\/strong> or Depth First Search<\/strong> to traverse each vertex of the graph.<\/p>\n<\/blockquote>\n

\"\"<\/p>\n

Description :<\/h4>\n
\n

We are using Breadth First Search<\/strong> or BFS<\/strong> to find minimum number of edges between source (s<\/code>) & destination (d<\/code>) vertex. We will maintain a distance[ ]<\/strong> array (initally 0), it will store the distance of ith<\/code> vertex at ith<\/code> index starting from s<\/code>.
\nStarting from s<\/code>, it is at distance 0 from itself, traverse all the vertex adjacent to s<\/code> and update their distances (distance = distance[s] + 1)<\/code>, since each vertex is adjacent to s<\/code> and at distance 1<\/code> from it, it will take (distance[s]+1)<\/code> distance to reach them from s<\/code>. Now consider all the vertices adjacent to the vertex adjacent to s<\/code> . These are all at distance (distance[s]+2)<\/code> from s<\/code> and so on. <\/p>\n

In this way, we will visit every non-visited vertex (x<\/code>) which is adjacent to some vertex (y<\/code>) and store its distance as distance[x]=distance[y]+1<\/code>. Finally we can get the distance of our destination vertex d<\/code> at distance[d]<\/code>.<\/p>\n<\/blockquote>\n

Algorithm :<\/h3>\n
<\/blockquote>\n

Breadth First Search<\/strong> :<\/h4>\n
\n
    \n
  1. Create a queue q<\/code> which will contain the vertices to be processed and a Boolean array visited[]<\/code> (initally false<\/strong>, as no vertex has been visited yet) which indicates for each vertex, if it has been visited or not.<\/li>\n
  2. Initially, push the source s<\/code> to the q<\/code> and set visited[s]=true<\/code>. <\/li>\n
  3. Then, loop until the queue is empty and in each iteration :<\/li>\n
  4. pop a vertex (x<\/code>) from the front of the queue.
    \nIterate through all the adjacent vertices i<\/code> of vertex x<\/code> and if some of these vertices i<\/code> that are not already visited (visited[i]=false<\/code>), mark them as visited (visited[i]=true<\/code>) and push them in the queue.<\/li>\n
  5. Stop when q<\/code> is empty.<\/li>\n<\/ol>\n<\/blockquote>\n

    Solutions:<\/h3>\n

    \t\t\t\t\t\t