laajuushaku

Laajuushaku, also known as breadth-first search (BFS), is a graph traversal algorithm. It starts at a designated root node and explores all the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. This means it explores the graph in layers.

The algorithm uses a queue data structure to keep track of the nodes to visit. When a node is visited, its unvisited neighbors are added to the queue. This process continues until all reachable nodes have been visited. Laajuushaku is guaranteed to find the shortest path in an unweighted graph, meaning the path with the fewest edges, from the starting node to any other node.

Common applications of laajuushaku include finding the shortest path in networks, web crawling, and solving puzzles like the Rubik's Cube. Its systematic layer-by-layer exploration makes it suitable for problems where finding the minimum number of steps is important. The time complexity of laajuushaku is typically O(V + E), where V is the number of vertices and E is the number of edges in the graph, as each vertex and edge is visited at most once. Its space complexity is O(V) in the worst case, as the queue can hold all vertices.