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
int findMaxUtil(Node node, Res res) {
if (node == null)
return 0;
int l = findMaxUtil(node.left, res);
int r = findMaxUtil(node.right, res);
int max_single = Math.max(Math.max(l, r) + node.data, node.data);
int max_top = Math.max(max_single, l + r + node.data);
res.val = Math.max(res.val, max_top);
return max_single;
}
int findMaxSum() {return findMaxSum(root);}
int findMaxSum(Node node) {
Res res = new Res();
res.val = Integer.MIN_VALUE;
findMaxUtil(node, res);
return res.val;
}
BFS - Stack Kullanarak Dolaşma
Örnek
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;
}
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)
