Graph Traversal Algorithms
For this activity, you will need to be using an Integrated Development Environment (IDE). The recommended IDE for this module is JetBrains IntelliJ IDEA for Python and JetBrains CLion for C++. You can follow instructions at the following page to set up your development environment:
Setting up your Development Environment
The work undertaken for this lab activity will build upon the work that you have done in the previous activity. If you have not done so already, it is recommended that you revisit the previous lab activity and complete those tasks.
Task 1 - Implementing the Depth-First Search Algorithm
For this task, you will need to implement the Depth-First Search (DFS) algorithm. The algorithm should be able to traverse the graph below and provide a solution.
The output from your solution should look something similar to what is shown below.
visited = ['A', 'E', 'H', 'F', 'D', 'C', 'G']
unvisited = ['B']
Task 2 - Implementing the Breadth-First Search Algorithm
For this task, you will need to implement the Breadth-First Search (BFS) algorithm. The algorithm should be able to traverse the graph below and provide a solution.
The output from your solution should look something similar to what is shown below.
visited = ['A', 'B', 'C', 'D', 'E']
Task 3 - Implementing Dijkstra's Algorithm
For this task, you will need to implement the Dijkstra's algorithm. The algorithm should be able to traverse the graph below and provide a solution.
The output from your solution should look something similar to what is shown below. The output will consist of a list of nodes which is the lowest cost path, along with the overall cost itself.
path = ['O', 'A', 'B', 'D', 'T']
totalCost = 13
Struggling?
If you are struggling with this lab activity, you may want to get some additional support. You can speak to the module leader/team in the room of when the lab week is active, or you can visit the Additional Support page for more information on how you can get extra support.