LeetCode Breadth First Search

Giriş
Breadth-First Search (BFS)- önce bir alt seviyedeki tüm çocukları dolaşır. Açıklaması şöyle

The thing about BFS, is that it traverses the graph level by level. Meaning that first it traverses all the vertices at a distance of 1 from the source vertex. Then it traverses all the vertices at a distance of 2 from the source vertex and so on.

BFS düğümü bir sol bir da sağ olmak üzere iki alt düğüm içerir. Tanımlamak için şöyle yaparız.

struct Node {
  Node* right;
  Node* left;
};

Dolaşma Sırası
Aşağıdaki ağaç yapısını BFS ile dolaşmak istersek sıralama şöyle olur. 1 sonra  2, 3 sonra 4,5,6 vs.

       1 
     /   \   
    2     3   
   / \     \   
  4   5     6   
 /           \ 
7             8

Complexity
Açıklaması şöyle

BFS runs in O(V + E) time provided the graph is represented by the adjacency list structure.

In the dense case also, you will see the answer will be O(V+E). (Representation is adjacency list).

In case of Adjacency matrix O(V^2).

Binary Search İle Farkı
Binary Search yani ikilik aramanın amacı en az sayıda düğümü dolaşmak, BFS'nin amacı ise tüm düğümleri belli bir sıra ile dolaşmak. Binary Search ile arama yapmak için şöyle yaparız.

Node* find(int v) {
  Node* temp = root;  
  while (temp != nullptr) {
    if (temp->data == v) {
      return temp;
    }
    else {
      if (v > temp->data) {
        temp = temp->right;
      }
      else {
        temp = temp->left;
      }
    }
  }
  return nullptr;
}

BFS - Özyinelemeli Dolaşma
Kodda önce left_subtree() daha sonra right_subtree() recursive (öz yinelemeli) olarak

Örnek

Şöyle yaparız. Burada tree bir map'e dolduruluyor. Böylece her seviyedeki nesneye kolayca erişilebiliyor.

typedef std::map<int, std::vector<node>> nodes_by_level;

join_siblings(int level, const tree& t, nodes_by_level& nodes) {
  if (t.root()) { 
    nodes[level].push(t.root());
    join_siblings(level + 1, t.left_subtree(), nodes);
    join_siblings(level + 1, t.right_subtree(), nodes);
  }
}

nodes_by_level join_siblings(const tree& t) {
  nodes_by_level nodes;
  join_siblings(0, t, nodes);
  return nodes;
}

Örnek

Soru Maximum Path Sum in a Binary Tree. Şöyle yaparız. Burada aslında yapılan hesaplamayı dikkate almazsak, klasik bir recursive BFS görebiliriz.

int findMaxUtil(Node node, Res res) { 
  if (node == null) 
    return 0; 
  
  // l and r store maximum path sum going through left and 
  // right child of root respectively 
  int l = findMaxUtil(node.left, res); 
  int r = findMaxUtil(node.right, res); 
  
  // Max path for parent call of root. This path must 
  // include at-most one child of root 
  int max_single = Math.max(Math.max(l, r) + node.data, node.data); 
    
  // Max Top represents the sum when the Node under 
  // consideration is the root of the maxsum path and no 
  // ancestors of root are there in max sum path 
  int max_top = Math.max(max_single, l + r + node.data); 
  
  // Store the Maximum Result. 
  res.val = Math.max(res.val, max_top); 
  
  return max_single; 
} 

int findMaxSum() {return findMaxSum(root);} 
  
// Returns maximum path sum in tree with given root 
int findMaxSum(Node node) { 
  // Initialize result 
  // int res2 = Integer.MIN_VALUE; 
  Res res = new Res(); 
  res.val = Integer.MIN_VALUE; 
  
  // Compute and return result 
  findMaxUtil(node, res); 
  return res.val; 
} 

BFS - Stack Kullanarak Dolaşma

Örnek

Şöyle yaparız

public List<Integer> closestKValues(TreeNode root, double target, int k) {
  // 1. Create a Priority Queue, sorted on diffs
  PriorityQueue<double[]> pq = new PriorityQueue<double[]>(
    Comparator.comparing(a -> a[1]));
  Stack<TreeNode> stack = new Stack<>();

  stack.push(root);

  // 2. Traverse tree iteratively and place items in PQ
  while (!stack.isEmpty()) {
    TreeNode current = stack.pop();
	
    pq.add(new double[] {current.val /* value */,
                         Math.abs(current.val - target/* diff */ )});
	
    if (current.left != null) {
      stack.push(current.left);
    }
	
    if (current.right != null) {
      stack.push(current.right);
    }        
  }

  // 3. Prepare the output with needed K-values.
  List<Integer> result = new ArrayList<>();

  for (int i = 0; i < k; ++i) {
    if (!pq.isEmpty()) {
      result.add((int) pq.poll()[0]);
    }
  }
  return result;
}

BFS - Liste Kullanarak Dolaşma
Açıklaması şöyle.

In a BFS, you use a queue. If you come across an unseen node, you add it to the queue.

Örnek
Elimizde şöyle bir ağaç olsun.

   5
  / \
2     15
     /
    10
   / \ 
  6   14

Şöyle yaparız. Burada Tree bir listee dolduruluyor

public void bfs (Tree T)
{
  
  List<Tree> list = new List<Tree>();
  
  if (T == null)
    return ;
   
  list.Add(T);

  while (list.Count != 0)
  {
    Tree currNode = list.pop ();

    if (currNode.l != null)
    {
      ...
      list.Add(currNode.l);
    }
    if (currNode.r != null)
    {
      ...
      list.Add(currNode.r);
    }
  }
  
}

BFS İle Maze (Labirent) veya Izgara (Grid) Dolaşma
- Bu tarz sorular mülakatlarda çokça soruluyor. Genellikle bir kuyruk kullanılarak çözülür.

- BFS ile Dijkstra's Shortest Path çok benziyorlar. Aralarındaki en önemli fark BFS komşuları kuyruğa eklerken herhangi bir kritere bakmaz. Shortest Path ise en kısa yolu seçer.

Örnek
Labirentte alıcılar/mayınlar varsa bunların etrafından dolaşarak en soldan en sağa geçiş isteyelim. Adımlar şöyle

Başlamadan Önce
Elimizde kareleri temsil eden şöyle bir yapı olsun

struct Node {
  
  int x
  int y;
  int distance
}

Ayrıca dolaşılan düğümleri sakladığımız bir dizi olsun

boolean [][] visited = new boolean [M][N];

1. Başlamadan önce alıcıların ve etrafındaki 8 hücrenin konumlarını işaretle. Bu hücreleri uğranmayacak (tehlikeli) olarak bir sabitle işaretle.
2. Başlamadan önce normal hücrelerin mesafe bilgisini sıfırla.

Algoritma
1. En soldaki tüm sütunları eğer alıcılar yüzünden tehlikeli değilse BFS kuyruğuna ekle.
2. do till queue is not empty - kuyrukta eleman var olduğu sürece
  a) Kuyruktan bir eleman al
  b) Eğer hedef konum ise çık
  c) Değilse etrafındaki 4 tane kareyi eğer alıcı yoksa kuyruğa ve uğranmamışsa ziyaret edildi olarak işaretle, ayrıca mesafeyi artır  ve kuyruğa ekle
3. Eğer kuyruk boşaldı ve hedefe varılması ise false dön


Örnek
Kendimden iki düğüm ötedeki çocukları dahil ederek dolaşmak istersek şöyle yaparız.

For each vertex v in V
{
  Do a BFS with v as source vertex
  {
    For all vertices u at distance of 2 from v
    add u to adjacency list of v 
    and terminate BFS
  }
}

Örnek
Elimizde özel sadece şöyle dolaşabilen bir robot olsun. Yani sadece sağa veya aşağı gibebilsin.

(x,y)  ->  (x+y, y)
(x,y)  ->  (x, x+y)

Şöyle yaparız.

def can_reach_target(pos, target):
    if pos == target: 
        return True
    if pos[0] > target[0] or pos[1] > target[1]: 
        return False
    return can_reach_target((pos[0], sum(pos)), target) or \
           can_reach_target((sum(pos), pos[1]), target)