Breadth first search

Définition

xxxxxxx

Français

xxxxxxx

Anglais

breadth first search

Breadth-first search is best understood with respect to a tree, though it can be applied to graphs in general, provided a starting node is nominated.

A complete breadth first search traverses every node of the tree or graph, starting from the root node or starting node, first processing, checking, or inspecting the root/starting node. In future we'll just say it "processes" the node. Next it processes the neighbours of the root/starting node (in some order), and then the neighbours of the neighbours, and so on, until all the nodes have been processed.

In the case of a tree, no node will be visited twice - this is a property of trees. In the case of a graph, whether a directed acyclic graph or a general graph, some nodes will be visited twice. On the second and subsequent visits, the node and its neighbours should be ignored. Thus a breadth-first algorithm on such graphs needs to mark each node as visited when it first encounters it, and check each node it comes to process to see if it has already been visited.

For the tree shown below, the order of visiting for a breadth first search would be: A B C D E F G H I J

                    A
                   / \
                  /   \
                 B     C
                / \   / \
               D   E F   G
              /       \   \
             H         I   J

Compare depth first search.

Source : UNWS AI dictionary