Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləri

Çətinlik səviyyəsi Mühit
Genişlik İlk Axtarış Dərinlik İlk Axtarış nəzəriyyəBaxılıb 35

Əvvəlki yazıda (Qrafik və onun tətbiqi, BFS bir qrafikDFS bir qrafik) Qrafik keçidinin məntiqini və tətbiqini başa düşürük. İndi irəli baxırıq və BFS / DFS-nin tətbiqini və ehtiyaclarını görürük.

Genişlik-İlk Axtarışın tətbiqi

BFS istifadə edərək verilmiş bir qrafikin əlaqəli komponentləri

Verilən bir qrafın əlaqəli komponenti, hər bir düyünün cütü bir yolla birləşdiriləcək şəkildə verilmiş bir qrafın qovşaqlarının toplusu olaraq təyin olunur. Bağlı komponentin bütün cütlüyünün fərqli olduğunu və bütün dəstlərin (bağlı komponentlərin) birləşməsinin ümumi zirvələrin sayına bərabər olacağını qeyd edin. Aşağıdakı qrafikin 4 əlaqəli komponenti var:

Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləriPin

Verilən bir qrafın əlaqəli komponentini tapmaq üçün dəvət olunmayan bütün təpələr üçün BFS / DFS istifadə edirik. BFS və DFS istifadə edərək hər iki məntiq üçün yalançı kodu görək.

Print the connected component of a given graph and each set of vertices for a connected component separated by a new line.
There are two approaches-

Using BFS:
Step:1 Set all vertices as unvisited(false).
Step:2 Traverse all the vertices of the graph and perform the following operation:
       a) If the current vertex is unvisited then call DFS_CALC(vertex_v).
       b) Move to the next line(use endl).
BFS_CALC(vertex_v):
Step:1 Inserting vertex_v in queue and mark as visited.
Step:2 Process till queue.empty()==false
       a) Find the first element of the queue and pop it and store it in the top variable.
       b) Processing all the connected vertex of the top:
           i) for all connected vertex(c_v) of top in graph:
                  if(c_v is unvisited) then: queue.push(c_v) and mark c_v as visited.    

Using DFS:
Step:1 Set all vertices as unvisited(false).
Step:2 Traverse all the vertices of the graph and perform the following operation:
       a) If the current vertex is unvisited then call DFS_CALC(current vertex).
       b) Move to the next line (use endl).
DFS_CALC(vertex_v):
Step:1 Print vertex_v.
Step:2 Mark vertex_v as visited(true).
Step:3 Now call DFS_CALC(u) for every connected vertex(u) to vertex_v and if the connected vertex(u) is unvisited.

Bir qrafikin iki tərəfli olub olmadığını və ya BFS istifadə etmədiyini yoxlayın

İki tərəfli qraf, köşələri iki A, B dəstinə bölən qrafiqdir. Hər kənarın A-da bir başqa, B-də başqa bir təpə var. Başqa sözlə desək, A və ya çoxluqların təpələri arasında kənar olmadığını deyirik. B burada birləşmə B = V (qrafikin bütün təpələrinin dəsti) və A kəsişməsi B = NULL. Daha yaxşı başa düşmək üçün nümunəyə baxaq:

Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləriPin

Yuxarıdakı qrafın təpələrinin A dəsti {1,3,5,7} və yuxarıdakı qrafın təpələrinin B dəsti {2,4,6,8}.

Grafiğin iki tərəfli olduğunu tapmaq üçün BFS-dən istifadə edirik və ya zirvələrə 0,1 təyin edirik. A dəsti üçün 0, B dəsti üçün 1 idik və təyin etdikdən sonra eyni təyin olunmuş dəyərə sahib olan iki təpənin kənar içərisində olub-olmadığını yoxladıq. Əgər təpələr arasında tapılan heç bir kənar eyni qiymətə (0,1) bərabər deyilsə, onda qrafikin iki tərəfli olduğunu deyirik. Yuxarıdakı məntiq üçün yalançı kodu görək:

Pseudo-Code
Step:1 Assign 0 to the starting vertex(source vertex) and put it into set A.
Step:2 Set 1 for all the neighbors of the previous vertex(of set A) and putting them into set B.
Step:3 Set 0 to all the neighbor's neighbor.
Step:4 Follow the above process until we assign (0,1) to all the vertices.
Step:5 While assigning the values if we find edges between the vertices whose assigned value is the same then the print graph is "not bipartite".

BFS istifadə edərək yönləndirilməmiş qrafikdə dövr aşkarlanması

Döngə aşkarlanması üçün bir sıra məlumat strukturundan istifadə edirik. BFS-ni bir təpədə tətbiq etdikdə və növbədə olan hər hansı bir bağlı nodu tapdıqda (ziyarət olunan node-ya) qrafikin bir dövrü olduğunu söyləyirik. Daha yaxşı başa düşmək üçün nümunəyə baxaq:

Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləriPin

Burada ziyarət edilən cari təpənin 5 olduğunu və 4-ün onsuz da növbədə olduğunu və 5-in əlaqəli təpəsini də gördük. Sonra verilmiş qrafikdə bir dövr olduğunu söyləyirik (Burada 3-4-5 -3 yalnız qrafikdə mövcud olan dövrdür).

Pseudo-Code:
Step:1 Apply BFS to all the unvisited vertex of the graph.
Step:2 If we find any connected node(wrt current vertex) which is already visited and not the parent of 
       the current vertex then we say that there is a cycle in graph otherwise no cycle in the graph.

BFS istifadə edərək çəkisiz qrafik üçün ən qısa yol

Ağırlaşdırılmamış qrafik üçün ən qısa yolu tapmaq üçün BFS-dən istifadə edirik. BFS tətbiq edərkən verilmiş zirvələrin sələfini saxlayırıq. Bu məntiq eyni zamanda qrafikdə göstərilən mənfi ağırlıq dövrləri üçün də işləyəcəkdir. 1-7 arasında ən qısa yolu tapın. Burada 1-2-4-7 və 1-2-5-7 uzunluğu 3 olan ən qısa iki yoldur.

Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləriPin

Məntiqin yalançı kodunu görək:

Pseudo-Code:
Step:1 Set all the vertices as unvisited(visited[v]=false).
Step:2 Set distance for all vertices as infinity(distance[v]=INF).
Step:3 Set predecessor of every vertex as -1(predecessor[v]=-1).
Step:4 Now first vertex to be visited.
       i) set visited[start]=true.
       ii) distance[start]=0 because the distance between the start to start is 0.
       iii) queue.push(start).
Step:5 While(!queue.empty()) then:
       i) Read a vertex(front) from the queue.
       ii) For all connected vertices of front which are unvisited:
            a) Make it visited.
            b) The distance of connected vertex is: distance[front]+1.
            c) Predecessor of connected vertex is front(predecessor[front][i]=front).
            d) queue.push(v[front][i]) where v[front][i] is connected vertex of front.
            e) if(destination==v[front][i]) then return true.
Step:6 return false.
Step:7 Print the length of the shortest path by print distance[destination].
Step:8 Print the path of the shortest path by print the predecessor from the destination to starting.

BFS-nin digər tətbiqləri də var:

  • Sosial Şəbəkə Veb saytları (Facebook kimi).
  • GPS naviqasiya sistemləri.
  • Şəbəkədə yayım.
  • Peer to Peer Şəbəkələri.
  • Zibil Kolleksiyasında istifadə olunur.
  • Axtarış motorlarındakı tarayıcılar.
  • Yol tapmaq
  • Ford-Fulkerson Alqoritmi.

Dərinlik-Birinci Axtarışın tətbiqi

DFS istifadə edərək yol tapmaq

İstifadəsi ilə DFS, iki təpə arasındakı yolu tapırıq. Yalnız birinci zirvədə DFS tətbiq edin və dfs keçidindən istifadə edərək ikinci zirvəyə çatdığımızı yoxlayın.

Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləriPin

Pseudo-Code:
Step:1 Call DFS(start) where start as the first vertex.
Step:2 Use a stack to store the path between start vertex to current vertex.
Step:3 If(second_vertex==curent_vertex) then return the path using stack.

DFS istifadə edərək topoloji çeşidləmə

Təpələrin düzülüşüdür ki, vertikal u-dan v-yə yönəldilmiş hər bir uv kənar, düzəlişdə v təpədən əvvəl gəlsin. Topoloji çeşidləmə konsepsiyasından istifadə etməzdən əvvəl xatırlamaq lazım olan bir məqam:

a) Qrafik DAG olmalıdır (Birbaşa asiklik qrafik).

b) Hər DAG bir və daha çox topoloji sifarişə sahib olacaqdır.

Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləriPin

Pseudo-Code:
Step:1 vector ord that will contain the sorted nodes.
Step:2 Set all nodes as unvisited(false).
Step:3 While exists nods are unvisited then:
       select an unvisited node v and call topological(v).

topological(v):
Step:1 If v is visited then return.
Step:2 If v is unvisited then stop.
Step:3 Set v as unvisited(false).
Step:4 If u is the connected vertex of v then call topological(u) for all possible value of u.
Step:5 Set v as visited(true).
Step:6 Add v to the vector ord.
Step:7 Print vector ord.

DFS istifadə edərək qrafikin güclü bir şəkildə əlaqəli bir hissəsini tapın

Hər hansı bir cüt qovşaq arasında bir qrafın bağlı hissəsindəki bir yolla keçə bilsək, güclü bağlı deyilir. Qrafikin güclü birləşdirilmiş komponentini tapmaq üçün məntiq üçün nümunə və yalançı kodu görək.

Genişlik İlk Axtarış və Dərinlik İlk Axtarış tətbiqləriPin

Aşağıdakı (0,2,1) və (6,5,4,3) qrafikin SCC-si.

Pseudo-Code:
Step:1 Apply DFS(start) on the graph and store the finishing time of each node.
       DFS(start):
       i) visited[start]=true.
       ii) for all neighbours u of start that are unvisited:
           DFS(u).
       iii) stack.push(u).
Step:2 Reverse the graph.
       i) Clear the adjacency list.
       ii) for all edges between u to v:
           adjacency_list[v].push_back(u).
Step:3 Apply DFS from the vertex which is on the top of the stack.
       While(!stack.empty()):
       i) top=stack.top().
       ii) stack.pop().
           DFS(u).
       iii) if top is unvisited:
            DFS(top).
Step:4 When all nodes which are visited will form SCC.
Step:5 Repeat till we get a vertex from the top of the stack which is unvisited.

DFS-nin bəzi digər tətbiqləri də var:

  • Minimum yayılma ağacını tapın.
  • Qrafik iki tərəfli olub olmadığını yoxlayın.
  • Bulmacaları yalnız bir həll yolu ilə həll etmək.
  • Qrafın körpülərinin tapılması.
  • Planarlıq testi.
  • Qrafiklərdə əlaqə tapmaq.
  • Qrafikdə yayılmış meşənin tapılması.

References

Translate »