Pirmoji paieška (BFS) ir Giluminė paieška (DFS) yra du pagrindiniai algoritmai, naudojami grafikų ir medžių kirtimui arba paieškai. Šiame straipsnyje aprašomas pagrindinis skirtumas tarp paieškos pagal plotį ir paieškos pagal gylį.
Skirtumas tarp BFS ir DFS
Pirmoji paieška (BFS) :
BFS, „Breadth-First Search“, yra viršūnėmis pagrįsta technika, skirta rasti trumpiausią kelią grafike. Jis naudoja a Išvestis:
A, B, C, D, E, F>
Kodas:
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; vieša: Grafas(int V); // Konstruktorius // funkcija pridėti briauną į grafiką void addEdge(int v, int w); // spausdina BFS traversal iš nurodyto šaltinio s void BFS(int s); }; Grafikas::Grafas(int V) { this->V = V; adj = naujas sąrašas [V]; } void Grafas::addEdge(int v, int w) { adj[v].push_back(w); // Pridėkite w prie v sąrašo. } void Graph::BFS(int s) { // Pažymėti visas viršūnes kaip neaplankytas bool* visited = new bool[V]; už (int i = 0; i< V; i++) visited[i] = false; // Create a queue for BFS list eilė; // Pažymėkite dabartinį mazgą kaip aplankytą ir įtraukite jį į eilę [s] = true; eilė.push_back(s); // 'i' bus naudojamas visoms gretimoms // viršūnių sąrašo viršūnėms gauti ::iteratorius i; // Sukurkite susiejimą iš sveikųjų skaičių į simbolius char map[6] = { 'A', 'B', 'C', 'D', 'E', 'F '}; while (!queue.empty()) { // Įtraukite viršūnę iš eilės ir išspausdinkite ją 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(() =>[]); // Gretumų sąrašų masyvas } // Funkcija pridėti briauną į grafiką addEdge(v, w) { this.adj[v].push(w); // Pridėkite w prie v sąrašo. } // Funkcija atlikti BFS perėjimą iš nurodyto šaltinio s BFS(s) { // Pažymėti visas viršūnes kaip neaplankytas let visited = new Masyvas(this.V).fill(false); // Sukurti eilę BFS let queue = []; // Pažymėkite dabartinį mazgą kaip aplankytą ir įtraukite jį į eilę [s] = true; queue.push(s); // Susiejimas iš sveikųjų skaičių į simbolius tegul map = ['A', 'B', 'C', 'D', 'E', 'F']; while (queue.length> 0) { // Įtraukite viršūnę iš eilės ir išspausdinkite ją s = queue.shift(); console.log(žemėlapis [s] + ' '); // Naudokite susiejimą, kad atspausdintumėte originalią etiketę // Gauti visas gretimas ištrauktos viršūnės viršūnes s // Jei gretimas nebuvo aplankytas, pažymėkite jį aplankytą // ir įtraukite jį į eilę (tegul i of this.adj[s ]) { if (!aplankė[i]) { eilė.push(i); aplankytas [i] = tiesa; } } } } } // Pagrindinė funkcija funkcija main() { // Sukurkite diagramoje pateiktą grafiką /* A / B C / / D E F */ tegul 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 yra: '); g.BFS(0); // Paleisti BFS nuo A (0) } // Paleisti pagrindinę funkciją main();>>
Išvestis Breadth First Traversal is: A B C D E F>
Pirma giluminė paieška (DFS) :
DFS, Gylis pirmoji paieška , yra briaunomis pagrįsta technika. Jis naudoja Išvestis: