DFS is an algorithm to search a graph for a path from one vertex (node) to another. It just tells you if there is a path or not, nothing more. There can be many paths from one vertex to another. It will just choose one that it meets first; it doesn't care about how long the path is. The pseudocode to implement this algorithm uses an array variable to store the nodes that have been already explored so that the search won't go back to the already explored nodes. We still another (Map) variable to trackback the path or to know the parent or preceding node of the current node. There can be more than parent or preceding nodes but there is only one that the search crosses to reach the current node.
BFS is also an algorithm to search for a path in a graph or tree. It is based on DFS but it can find the shortest path. In processing, DFS uses stack data structure but BFS uses queue data structure. In the pseudocode from my teacher below looks like it does not have anything to do with path cost. And the only difference between it and DFS's pseudocode is frontier variable uses queue, not stack.
UCS use priority queue to store the explored nodes and their cumulative path costs so that it can find the shortest path. I'm not sure how BFS is different from UCS. The algorithm below is from my teacher. In the third line from top and another third line from bottom, it should have said cumulative PATH-COST instead of only PATH-COST.
My homework is to implement DFS, BFS and then UCS in R programming. The source code can be found here https://github.com/vathanakmao/ai-assignments
No comments:
Post a Comment