CISC 235 Lecture Notes - Lecture 18: Popular Alternative, Tree Traversal, Binary Tree
21 Mar 2016
School
Department
Course
Professor
Document Summary
The most popular alternative to bfs is depth-first search. As the name suggests, dfs always tries to move forward to a new level before backing up and looking for another vertex at the current level. As before, we assume the start vertex is determined by some aspect of the algorithm that is calling. for each neighbour y of v such that y is not marked visited: # as with bfs, if we are building a tree then we make v the parent of y. Once again, the complexity of the algorithm depends on the implementation we choose to represent the vertices and edges of: the total number of recursive calls cannot exceed n, since each call marks a vertex. Within each recursive call the most time- consuming operation is finding the neighbours of the current vertex.
