Write a function that takes an undirected graph in adjacency-list representation and returns True if the graph contains a cycle. (Hint: an undirected graph is cyclic if a depth-first search ever encounters a node that has already been visited.)
Write a function that takes a directed graph and two vertex ids v and w, and returns the length of the shortest possible path from v to w. If w is not reachable from v, return -1.
Write a function that takes a directed graph and two vertex ids v and w, and returns a list of vertex ids containing a path from v to w that is as short as possible.
Write a function that takes a graph that is a tree, i.e. a connected, undirected, acyclic graph. The function should also take three vertex ids v, w, and x. The function should return true if w is between v and x, i.e. on the (unique) path that leads from v to x.
Write a program that reads a rectangular maze from standard input in the following format, where '#' represents a wall:
######## # # # # # # # # # # ## ## # ########
The program should print True if the maze is connected, i.e. every two empty squares in the maze are connected by some path. Otherwise print False.
Write a function that takes a 2-dimensional array of booleans representing a maze. There will be no wall in the upper-left or lower-right corner.
The procedure should print out the maze, indicating the shortest path from the upper-left corner to the lower-right corner. For example, the output might look like this:
..###### #.# # #.# # # #...# # ## ....# ######..
If no such path exists, print the maze without any path.