Pirmā meklēšana (BFS) un Dziļuma pirmā meklēšana (DFS) ir divi pamata algoritmi, ko izmanto grafiku un koku šķērsošanai vai meklēšanai. Šajā rakstā ir aprakstīta galvenā atšķirība starp meklēšanu pēc platuma un meklēšanu pēc dziļuma.
Atšķirība starp BFS un DFS
Pirmā meklēšana (BFS) :
BFS, Breadth-First Search, ir uz virsotnēm balstīts paņēmiens īsākā ceļa atrašanai grafikā. Tas izmanto a Izvade:
Linux make komanda
A, B, C, D, E, F>
Kods:
C++ #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; public: Graph(int V); // Konstruktors // funkcija malas pievienošanai grafikam void addEdge(int v, int w); // izdrukā BFS traversal no dotā avota s void BFS(int s); }; Grafs::Grafs(int V) { this->V = V; adj = jauns saraksts [V]; } void Graph::pievienotEdge(int v, int w) { adj[v].push_back(w); // Pievienojiet w v sarakstam. } void Graph::BFS(int s) { // Atzīmēt visas virsotnes kā neapmeklētas bool* visited = new bool[V]; for (int i = 0; i< V; i++) visited[i] = false; // Create a queue for BFS list rinda; // Atzīmēt pašreizējo mezglu kā apmeklētu un ievietojiet to rindā [s] = true; queue.push_back(s); // 'i' tiks izmantots, lai iegūtu visas // virsotņu saraksta blakus esošās virsotnes ::iterators i; // Izveidojiet kartējumu no veseliem skaitļiem līdz rakstzīmēm char map[6] = { 'A', 'B', 'C', 'D', 'E', 'F '}; while (!queue.empty()) { // Iekļaujiet virsotni rindā un izdrukājiet to 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(() =>[]); // Blakusumu sarakstu masīvs } // Funkcija malas pievienošanai grafikam addEdge(v, w) { this.adj[v].push(w); // Pievienojiet w v sarakstam. } // Funkcija, lai veiktu BFS iziešanu no dotā avota s BFS(s) { // Atzīmēt visas virsotnes kā neapmeklētas let visited = new Array(this.V).fill(false); // Izveidot rindu BFS let queue = []; // Atzīmējiet pašreizējo mezglu kā apmeklētu un ievietojiet to rindā [s] = true; queue.push(s); // Kartēšana no veseliem skaitļiem uz rakstzīmēm let map = ['A', 'B', 'C', 'D', 'E', 'F']; while (queue.length> 0) { // Atvienojiet virsotni no rindas un izdrukājiet to s = queue.shift(); console.log(karte [s] + ' '); // Izmantojiet kartēšanu, lai drukātu oriģinālo etiķeti // Iegūt visas blakus esošās virsotnes virsotnes, kas atrodas rindā ]) { if (!apmeklēja[i]) { rinda.push(i); apmeklēja [i] = patiess; } } } } } // Galvenā funkcija funkcija main() { // Izveidojiet diagrammā norādīto grafiku /* 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('Breadth First Traversal ir: '); g.BFS(0); // Sākt BFS no A (0) } // Palaidiet galveno funkciju main();>>
Izvade Breadth First Traversal is: A B C D E F>
Pirmā dziļuma meklēšana (DFS) :
DFS, Pirmā dziļuma meklēšana , ir uz malām balstīta tehnika. Tas izmanto Izvade: