---------------------------------------------------------------- Assignment 1: Implementing Depth-First Search ---------------------------------------------------------------- A directed acyclic graph (DAG) consists of a set of nodes and a set of directed arcs (also known as directed edges) between those nodes. For example, the following is a DAG. A --> C --> D --> F \ \ ^ \ \ | \ \--> E --+ \ \ \--> B \ \--> G Using LISP one might represent this as follows: (defvar *graph* '((Nodes (A B C D E F G)) (Edges ((A C) (A B) (C D) (C E) (D F) (E F) (E G))))) Something you do frequently with DAGs is SEARCH: start at a node, and find. For example, in the above graph a search starting at D for target node F would succeed, but a search starting at D for target node B would fail. Search of this kind is the heart of a great deal of work in artificial intelligence; for example, game-playing programs (for tic-tac-toe, chess, checkers, backgammon, etc.) often view the game as a search for a winning board configuration, and parsing a sentence can be viewed as searching for a legal parse tree that fits the sentence. There are different algorithms for searching a graph, but here is one of the most common: depth-first search. Algorithm DFS(start-node target) Create a list S, initially containing start-node as its only member While (S is not empty) Pop the top node x off S (that is, S is being treated as a stack) If x is the target Report success and quit --- we found the target! For each edge (x, y) in the graph, i.e. for each edge departing x, Put y on the front of list S (that is, push y onto stack S) Report failure --- target can't be reached from start-node! Your assignment, due in class next week, is to implement this algorithm -- please turn in hardcopies of a program listing and a few examples of the algorithm running on the above graph, with at least one success and one failure. Feel free to add statements to the program that print out messages as the search is in progress letting you know what's going on. For those who have less programming experience, I recommend simulating the algorithm by hand with pencil and paper for one or two cases first. For those with more programming experience, or for whom this is easy, let me suggest the following two optional extensions: (1) Modify the algorithm and implementation so that cycles in the graph don't cause you to go into an infinite loop (2) Modify the algorithm and implementation so that on success the program returns its path through the graph rather than just saying it succeeded. Feel free to talk to each other, but make sure that you turn in assignments individually and that what you turn in is sufficiently your own work to meet the University's standards for academic integrity. Have fun!

Return to the course home page.