Iskanje v širino (BFS) in Iskanje najprej v globino (DFS) sta dva temeljna algoritma, ki se uporabljata za prečkanje ali iskanje grafov in dreves. Ta članek obravnava osnovno razliko med iskanjem v širino in iskanjem v globino.
Razlika med BFS in DFS
Iskanje v širino (BFS) :
BFS, iskanje v širino, je tehnika, ki temelji na vozliščih za iskanje najkrajše poti v grafu. Uporablja a Izhod:
A, B, C, D, E, F>
Koda:
listnodeC++
#include #include using namespace std; // This class represents a directed graph using adjacency // list representation class Graph { int V; // No. of vertices // Pointer to an array containing adjacency lists list * adj; javno: Graf(int V); // Konstruktor // funkcija za dodajanje roba grafu void addEdge(int v, int w); // natisne prehod BFS iz danega vira s void BFS(int s); }; Graf::Graf(int V) { this->V = V; adj = nov seznam [V]; } void Graph::addEdge(int v, int w) { adj[v].push_back(w); // Dodaj w na v-jev seznam. } void Graph::BFS(int s) { // Označi vse točke kot neobiskane bool* visited = new bool[V]; za (int i = 0; i< V; i++) visited[i] = false; // Create a queue for BFS list čakalna vrsta; // Označi trenutno vozlišče kot obiskano in ga postavi v čakalno vrsto visited[s] = true; queue.push_back(s); // 'i' bo uporabljen za pridobitev vseh sosednjih tock // seznama tock ::iterator i; // Ustvari preslikavo iz celih števil v znake char map[6] = { 'A', 'B', 'C', 'D', 'E', 'F '}; while (!queue.empty()) { // Odstrani točko iz čakalne vrste in jo natisni s = queue.front(); cout<< map[s] << ' '; // Use the mapping to print // the original label queue.pop_front(); // Get all adjacent vertices of the dequeued vertex // s If a adjacent has not been visited, then mark // it visited and enqueue it for (i = adj[s].begin(); i != adj[s].end(); ++i) { if (!visited[*i]) { queue.push_back(*i); visited[*i] = true; } } } } int main() { // Create a graph given in the diagram /* A / B C / / D E F */ Graph g(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(2, 5); cout << 'Breadth First Traversal is: '; g.BFS(0); // Start BFS from A (0) return 0; }> Python from collections import deque # This class represents a directed graph using adjacency list representation class Graph: def __init__(self, V): self.V = V # No. of vertices self.adj = [[] for _ in range(V)] # Adjacency lists # Function to add an edge to graph def addEdge(self, v, w): self.adj[v].append(w) # Add w to v’s list # Prints BFS traversal from a given source s def BFS(self, s): # Mark all the vertices as not visited visited = [False] * self.V # Create a queue for BFS queue = deque() # Mark the current node as visited and enqueue it visited[s] = True queue.append(s) # Create a mapping from integers to characters mapping = ['A', 'B', 'C', 'D', 'E', 'F'] while queue: # Dequeue a vertex from queue and print it s = queue.popleft() # Use the mapping to print the original label print(mapping[s], end=' ') # Get all adjacent vertices of the dequeued vertex s # If an adjacent has not been visited, then mark it visited # and enqueue it for i in self.adj[s]: if not visited[i]: queue.append(i) visited[i] = True if __name__ == '__main__': # Create a graph given in the diagram # A # / # B C # / / # D E F g = Graph(6) g.addEdge(0, 1) g.addEdge(0, 2) g.addEdge(1, 3) g.addEdge(2, 4) g.addEdge(2, 5) print('Breadth First Traversal is: ', end='') g.BFS(0) # Start BFS from A (0)> JavaScript // This class represents a directed graph using adjacency list representation class Graph { constructor(V) { this.V = V; // No. of vertices this.adj = new Array(V).fill(null).map(() =>[]); // Niz seznamov sosednosti } // Funkcija za dodajanje roba grafu addEdge(v, w) { this.adj[v].push(w); // Dodaj w na v-jev seznam. } // Funkcija za izvedbo prehoda BFS iz danega vira s BFS(s) { // Označi vsa vozlišča kot neobiskana let visited = new Array(this.V).fill(false); // Ustvari čakalno vrsto za BFS let queue = []; // Označi trenutno vozlišče kot obiskano in ga postavi v čakalno vrsto visited[s] = true; queue.push(s); // Preslikava iz celih števil v znake let map = ['A', 'B', 'C', 'D', 'E', 'F']; while (queue.length> 0) { // Odstrani točko iz čakalne vrste in jo natisni s = queue.shift(); console.log(map[s] + ' '); // Uporabite preslikavo za tiskanje izvirne oznake // Pridobite vsa sosednja vozlišča odstranjene točke s // Če sosednja točka ni bila obiskana, jo označite kot obiskano // in jo postavite v čakalno vrsto za (naj i of this.adj[s ]) { if (!visited[i]) { queue.push(i); obiskano[i] = res; } } } } } // Glavna funkcija function main() { // Ustvari graf, podan v diagramu /* A / B C / / D E F */ let g = new Graph(6); g.addEdge(0, 1); g.addEdge(0, 2); g.addEdge(1, 3); g.addEdge(2, 4); g.addEdge(2, 5); console.log('Prvi prehod širine je: '); g.BFS(0); // Zaženi BFS iz A (0) } // Zaženi glavno funkcijo main();> Izhod
Breadth First Traversal is: A B C D E F>
Iskanje najprej po globini (DFS) :
DFS, Najprej iskanje po globini , je tehnika, ki temelji na robu. Uporablja Izhod:
A, B, C, D, E, F>
Razlika med BFS in DFS:
| Parametri | BFS | DFS |
|---|---|---|
| Pomeni | BFS pomeni iskanje najprej v širino. | DFS je kratica za Depth First Search. |
| Struktura podatkov | BFS (Breadth First Search) uporablja podatkovno strukturo Queue za iskanje najkrajše poti. | DFS (Depth First Search) uporablja podatkovno strukturo Stack. |
| Opredelitev | BFS je pristop prečkanja, pri katerem se najprej sprehodimo skozi vsa vozlišča na isti ravni, preden preidemo na naslednjo raven. | DFS je tudi prehodni pristop, pri katerem se prehod začne pri korenskem vozlišču in nadaljuje skozi vozlišča, kolikor je to mogoče, dokler ne dosežemo vozlišča brez neobiskanih bližnjih vozlišč. |
| Konceptualna razlika | BFS gradi drevo nivo za nivojem. | DFS gradi drevesno poddrevo za poddrevo. |
| Uporabljen pristop | Deluje po konceptu FIFO (First In First Out). | Deluje po konceptu LIFO (Last In First Out). |
| Primerno za | BFS je bolj primeren za iskanje točk bližje danemu viru. | DFS je primernejši, ko so rešitve oddaljene od vira. |
| Aplikacije | BFS se uporablja v različnih aplikacijah, kot so bipartitni grafi, najkrajše poti itd. | DFS se uporablja v različnih aplikacijah, kot so aciklični grafi in iskanje močno povezanih komponent itd. |
Oglejte si tudi BFS proti DFS za binarno drevo za razlike za prehod binarnega drevesa.