Breddeførstsøgning

Breddeførstsøgning, often translated as breadth-first search (BFS), is a graph traversal algorithm that explores a graph level by level. It starts at a selected vertex and explores all of the neighbor vertices at the present depth before moving on to vertices at the next depth level. BFS is an important algorithm in computer science, particularly in the study of graphs.

The algorithm works by using a queue data structure. Initially, the starting vertex is added to the queue. Then, as long as the queue is not empty, the algorithm dequeues a vertex, visits it, and enqueues all of its unvisited neighbors. This process continues until all reachable vertices have been visited.

BFS is guaranteed to find the shortest path in terms of the number of edges between the starting vertex and any other vertex in an unweighted graph. This property makes it useful for a variety of applications, including finding the shortest path in a maze, checking for connectivity in a network, and building a search index for the World Wide Web. Other applications include finding all nodes within a given distance from a source node or determining if a graph is bipartite. Its systematic level-by-level exploration ensures that the first time a target node is encountered, it is via the shortest possible path from the source.