Uninformed Search Algorithms Explained in 2 Minutes!

Ajouté : 2026-06-07

[00:00:00]How exactly does a computer go about finding the shortest path for a graph when it doesn't have any prior information beforehand about where it's going? Well, there's an approach for this called uninformed search, and there are three specific algorithms within that, and they each think very differently. The first algorithm is called breadth-first search, or BFS.

[00:00:17]Breadth-first search explores [music] the graph layer by layer. You start at the root, you visit all the neighbor nodes, and then the next layer of neighbors, and so on. It uses a data structure called a queue, which operates on the first-in and first-out concept.

[00:00:30]This first step is to add the start node. The second is that you pop the front node of the queue, and then mark it as visited, and then you add all the unvisited neighbor nodes. And step three is to repeat the two previous steps. BFS is designed to guarantee the shortest path, but only when all of the costs of the edges within that path are the same.

[00:00:47]The second approach is called depth-first search, or DFS. [music] Depth-first search goes deep before going wide, which means that you pick a path and follow it until the end in the graph. It uses a data structure called a stack, which is a recursive method. So, step one is to push the start node that you're working with, then you pop the top of the node from the stack, push the unvisited neighbors of the current node, and number three is to backtrack when you get stuck. Depth-first search is a method that uses less memory than breadth-first search, but it won't always find the shortest path. That leads to approach number three, uniform cost search, or UCS. UCS handles weighted edges, and it always expands with the cheapest path first. It uses a data structure called a priority queue, which is sorted by the cumulative cost of the path. [music] Step one is to add the step with cost zero, or the start of it. Step two is to pop the lowest [music] cost node, and the third one is to add the neighbors with their total path cost, and finally repeat until you reach your end goal state. UCS is an optimal algorithm, as it always finds the minimal cost solution. So, to recap it all, BFS is for the shortest hops, DFS is for the deepest dive, and BFS and UCS are optimal and complete, with [music] UCS delivering the lowest cost possible. There are three strategies for uninformed search if you have zero knowledge of the goal and that's what [music] makes them uninformed. I'm making more videos like these in this search algorithm series. If you like [music] to be sure to also comment, subscribe, and share your thoughts down below. I'll see you in the next one.