Question

Submission Question: Recursion with Trees – Depth First Search & Breadth First Search

Write a Python program using the Python IDE based on recursion with trees that is both depth first and breadth first searches.

The Python program to be developed will demonstrate the use of both depth-first (DFS) and breadth-first (BFS) searches. A tree node structure will be developed that will be used both for DFS and BFS searches. The program will apply recursion both for the DFS and BFS searches to completion of the entire DFS and BFS. Also, the Python program will provide as output some of the intermediate nodes that are transverse during the execution of the DFS and BFS. This output of the intermediate nodes searched will demonstrate the different paths executed during a DFS versus BFS.

Problem

Develop functions to demonstrate understanding of implementing a recursive depth first search (DFS) and an iterative breadth first search (BFS) in Python using a simple graph made of nodes. This example will use nodes A, B, C, D, and E connected as follows:

           A -----
         /   \     |
       B-D-C   |
         \ | /    |
            E -----

The program must have the following:

Demonstration of writing a recursive depth first search (DFS) function.

Demonstration of writing an iterative breadth first search (BFS) function.

Documentation Guidelines:

Use good programming style (e.g., indentation for readability) and document each of your program parts with the following items (the items shown between the '<' and '>' angle brackets are only placeholders.  You should replace the placeholders and the comments between them with your specific information).  Your cover sheet should have some of the same information, but what follows should be at the top of each program's sheet of source code.  Some lines of code should have an explanation of what is to be accomplished, this will allow someone supporting your code years later to comprehend your purpose.  Be brief and to the point.  Start your design by writing comment lines of pseudocode.  Once that is complete, begin adding executable lines.  Finally run and test your program.

Deliverable(s):

Your deliverable should be a Word document with screenshots showing the source code and running results, and discuss the issues that you had for this project related to AWS and/or Python IDE and how you solved them for all of the programs listed above as well as the inputs and outputs from running them. Submit a cover sheet with the hardcopy of your work.

programming written in python code.

Answer 1

Screenshots of source code as requested are as follows:

Screenshot of the output of the code is as follows