Author: Pradeep Pant

# Create six vertices numbered 0 through 5. 
# Display the vertex dictionary
g = Graph()
for i in range(6):
    g.addVertex(i)
print(g.vertList)

# Add the edges that connect the vertices together
g.addEdge(0,1,5)
g.addEdge(0,5,2)
g.addEdge(1,2,4)
g.addEdge(2,3,9)
g.addEdge(3,4,7)
g.addEdge(3,5,3)
g.addEdge(4,0,1)
g.addEdge(5,4,8)
g.addEdge(5,2,1)
# Nested loop verifies that each edge in the graph is properly stored. 
for v in g:
   for w in v.getConnections():
       print("( %s , %s )" % (v.getId(), w.getId()))

# The Graph class, contains a dictionary that maps vertex names to vertex objects.
# Graph() creates a new, empty graph.
Graph()   

buildGraph()

#BFS begins at the starting vertex s and colors start gray to show that 
#it is currently being explored. Two other values, the distance and the 
#predecessor, are initialized to 0 and None respectively for the starting
#vertex. Finally, start is placed on a Queue. The next step is to begin 
#to systematically explore vertices at the front of the queue. We explore 
#each new node at the front of the queue by iterating over its adjacency 
#list. As each node on the adjacency list is examined its color is 
#checked. If it is white, the vertex is unexplored, and four things happen:
#	* The new, unexplored vertex nbr, is colored gray.
#	* The predecessor of nbr is set to the current node currentVert
#The distance to nbr is set to the distance to currentVert + 1
#nbr is added to the end of a queue. Adding nbr to the end of the queue 
#effectively schedules this node for further exploration, but not until all the 
#other vertices on the adjacency list of currentVert have been explored.

bfs()

# The Graph class, contains a dictionary that maps vertex names to vertex objects.
# Graph() creates a new, empty graph.
Graph()

# To represent the knight’s tour problem as a graph we will use the 
# following two ideas: Each square on the chessboard can be represented 
# as a node in the graph. Each legal move by the knight can be represented
# as an edge in the graph. 

knightGraph()

# The genLegalMoves function takes the position of the knight on the 
# board and generates each of the eight possible moves. The legalCoord 
# helper function makes sure that a particular move that is generated is 
# still on the board.
genLegalMoves()

# DFS implementation
        
# we will look at two algorithms that implement a depth first search. 
# The first algorithm we will look at directly solves the knight’s tour 
# problem by explicitly forbidding a node to be visited more than once. 
# The second implementation is more general, but allows nodes to be visited 
# more than once as the tree is constructed. The second version is used in 
# subsequent sections to develop additional graph algorithms.

# The depth first exploration of the graph is exactly what we need in 
# order to find a path that has exactly 63 edges. We will see that when 
# the depth first search algorithm finds a dead end (a place in the graph 
# where there are no more moves possible) it backs up the tree to the next
# deepest vertex that allows it to make a legal move.
        
# The knightTour function takes four parameters: n, the current depth in 
# the search tree; path, a list of vertices visited up to this point; u, 
# the vertex in the graph we wish to explore; and limit the number of nodes 
# in the path. The knightTour function is recursive. When the knightTour 
# function is called, it first checks the base case condition. If we have 
# a path that contains 64 vertices, we return from knightTour with a status 
# of True, indicating that we have found a successful tour. If the path is not 
# long enough we continue to explore one level deeper by choosing a new vertex 
# to explore and calling knightTour recursively for that vertex.

# DFS also uses colors to keep track of which vertices in the graph have been visited. 
# Unvisited vertices are colored white, and visited vertices are colored gray. 
# If all neighbors of a particular vertex have been explored and we have not yet reached 
# our goal length of 64 vertices, we have reached a dead end. When we reach a dead end we 
# must backtrack. Backtracking happens when we return from knightTour with a status of False. 
# In the breadth first search we used a queue to keep track of which vertex to visit next. 
# Since depth first search is recursive, we are implicitly using a stack to help us with 
# our backtracking. When we return from a call to knightTour with a status of False, in line 11, 
# we remain inside the while loop and look at the next vertex in nbrList.

knightTour()

Please check GitHub for the full working code.

I will keep adding more problems/solutions.

Stay tuned!

Ref:  The inspiration of implementing DS in Python is from this course