Task 1 - Maze¶

Maze: from each intersection in a maze, one could go left, right, up and/or down.

1. How would you represent a such maze as a graph? Write a C++ struct, that could be used as a node in a graph that represents a maze.
2. Describe how to find your way out of a maze. You happen to have in your pocket a big pouch full of old coins or a red crayon.

Task 2 - Graph¶

In this exercise it is assumed that the starting graph or digraph has the following property: for any two nodes x and y there is always a path from x to y and from y to x. In performing a BFS a so called BF-tree can be formed. Consider for example the above graph. If we use k as the starting node, one possible BF-tree that can be produced is the following:

The numbers beside the nodes are simply the order in which the nodes are added to the BF-tree. Suppose it is necessary to know what nodes are the leaves of the BF-tree. For the above tree the leaves are {d, g, e, a, f}.

A typical BFS produces the following results:

• the distance of each node from the starting node
• the parent of each node in the BF-tree

Write pseudocode for a BFS that also produces a set containing the leaves of the resulting BF-tree.