Breadth first search and depth first search
转载自ICS161,学英语,自娱自乐
Traversal of graphs and digraphs
To traverse(遍历) means to visit the vertices in some systematic order. You should be familiar with various traversal methods for trees:
preorder: visit each node before its children.
postorder: visit each node after its children.
inorder (for binary trees only): visit left subtree, node, right subtree.
We also saw another kind of traversal, topological ordering(拓扑排序), when I talked about shortest paths.
Today, we'll see two other traversals: breadth first search (BFS) and depth first search (DFS). Both of these construct spanning trees with certain properties useful in other graph algorithms. We'll start by describing them in undirected graphs, but they are both also very useful for directed graphs.