The bfs algorithm sets the value of each vertexs predecessor to point to the vertex object that enqueued it. Add code to the end of the word_ladder_BFS.py program that traverses the linked list of predecessor references from sage to fool. and prints the corresponding word ladder from fool to sage.

IN PYTHON

from build_graph import buildGraph

from graph_algorithms import bfs

g = buildGraph("words.dat")

print("word ladder graph:") for v in g: print(v)

print(" ============ bfs prints ======================= ")

bfs(g, g.getVertex("fool"))

print(" ================================================ ")

wordLadderList = [] v = g.getVertex("sage") # ADD CODE HERE