Resources

Video

Slides

Main activity

Example program

Here is a [Python] implementation of a graph, that uses a dictionary (dictionaries are very similar to hash tables).

Extension activity

Notes

Graph traversal algorithms

Graph traversal algorithms like pre-order, in-order, and post-order are primarily used to visit all the nodes in a graph, tree, or other data structure systematically.  Each traversal order serves different purposes and is commonly associated with tree data structures, especially binary trees. 

Let's break down each one:

Pre-order traversal:

In pre-order traversal, the algorithm visits the current node before its child nodes.

Purpose: It's useful for situations where you need to explore or process the root of the tree or graph first, then recursively visit its children.

Real-world example: Imagine you're cataloguing a library of books stored in a tree structure where each node represents a book, and each child represents a chapter or section of that book. Pre-order traversal would be like starting at the first book, noting its details, then moving to its chapters before proceeding to the next book.

In-order traversal:

In in-order traversal, the algorithm visits the left child, then the current node, and finally the right child.

Purpose: It's commonly used in binary search trees (BSTs) to visit all nodes in sorted order. It's useful for tasks like printing out the contents of the tree in sorted order or performing operations that require elements to be processed in a specific sequence.

Real-world example: Think of a company's organisational chart represented as a binary tree, where each node represents an employee, and left and right children represent subordinates. In-order traversal would list employees in ascending order of their positions, starting from the lowest-level employees and moving up through managers to the CEO.

Post-order traversal:

In post-order traversal, the algorithm visits the child nodes before the current node.

Purpose: It's often used in tasks that require processing the leaves of a tree first before processing the internal nodes. It's also useful in memory management scenarios or when dealing with resource deallocation.

Real-world example: Consider a file system represented as a tree structure, where each node is a directory or file, and the children are its contents. Post-order traversal would be like deleting the contents of a directory before deleting the directory itself to ensure that files are removed before directories.

Relationship to depth-first and breadth-first searching:

Depth-first search (DFS): All three traversal orders (pre-order, in-order, post-order) are forms of DFS. DFS explores as far as possible along each branch before backtracking. Pre-order, in-order, and post-order are simply variations in the order in which nodes are visited during this exploration.

Breadth-first search (BFS): BFS explores a graph level by level. It systematically explores all neighbour nodes at the present depth before moving to the nodes at the next depth level. BFS doesn't have the notion of pre-order, in-order, or post-order traversal because it doesn't follow a specific order like those traversal algorithms do. Instead, it focuses on exploring the breadth of the graph.