Balise : Éditeur de wikicode 2017 |
Balises : Nouvelle redirection Éditeur de wikicode 2017 |
| Ligne 1 : |
Ligne 1 : |
| | #REDIRECTION[[Algorithme de parcours en largeur ]] |
| | |
| | [[Catégorie:ENGLISH]] |
|
| |
|
| == en construction ==
| |
| [[Catégorie:Vocabulary]]
| |
| [[Catégorie:Intelligence artificielle]]
| |
| [[Catégorie:UNSW]] | | [[Catégorie:UNSW]] |
|
| |
|
| |
| == 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: <code>A B C D E F G H I J</code>
| |
| A
| |
| / \
| |
| / \
| |
| B C
| |
| / \ / \
| |
| D E F G
| |
| / \ \
| |
| H I J
| |
| Compare depth first search.
| |
|
| |
|
| |
| <small>
| |
|
| |
|
| [http://www.cse.unsw.edu.au/~billw/aidict.html Source : UNWS AI dictionary ] | | [http://www.cse.unsw.edu.au/~billw/aidict.html Source : UNWS AI dictionary ] |
Version du 23 septembre 2019 à 16:13
