A grid is a useful first graph because its vertices and edges are visible. Each walkable cell is a vertex. A permitted move to a neighboring walkable cell is an edge. We use four directions and give every edge cost one.
You need Python collections and functions. This first unit provides the graph primer and queue/stack terminology before the algorithms. If you have studied the C++ graph lessons, the concepts carry over, but C++ progress is not a prerequisite for this Python course.
A row is a string of dots and hashes. Dot means walkable, hash means blocked. Coordinates are (row, column), not screen (x,y). Increasing row moves downward; increasing column moves right.
An ordered list of offsets defines up, right, down and left. Check bounds before indexing. Without an explicit nonnegative bound, Python’s negative indexing can turn a move off the top into a move to the bottom.
The public helper rejects ragged grids, unknown characters and coordinates outside the grid. It returns an empty list for a blocked current cell, even if nearby cells are open.
rows = ["...", ".#.", "..."]
row, col = 0, 0
for dr, dc in [(-1,0),(0,1),(1,0),(0,-1)]:
nr, nc = row + dr, col + dc
if 0 <= nr < len(rows) and 0 <= nc < len(rows[0]) and rows[nr][nc] == ".":
print((nr,nc))Neighbor order makes later traversals reproducible. A grid can have multiple shortest paths. Our order breaks ties without pretending one equally short path is mathematically required. DFS is also sensitive to stack insertion order.
The lab bounds grids at 16 × 16 to keep event exports and animations inspectable. It validates the board at public calls and later records snapshots, so its teaching implementation has extra work beyond a minimal graph traversal. We will state those costs explicitly rather than hiding them behind the textbook O(V+E) bound.
rows = ["ab", "cd"]
print("Python -1 row:", rows[-1])
print("legal graph row:", 0 <= -1 < len(rows))
print("one-cell neighbors:", [])Complete the neighbor helper and test the center, a corner, a wall and a one-cell grid. Do not add diagonals to make an unreachable example reachable; that would change the graph.
The final visualizer labels walls, start, goal, frontier, expanded cells and path cells with text as well as color. Next we separate the state needed to explore this graph.