Graph Implementations and Traversals Notes

Module 10: Graph Implementations and Traversals

Last Lecture Overview

  • Final Topic: Treating a maze as a graph.
  • Next Module: Introduction to graph algorithms, particularly the shortest path problem.

Graph Implementations and Traversals Recap

  • Passed previous lecture: Discussed graph implementation types and details about two main traversals:
    • Breadth First Search (BFS)
    • Uses a queue data structure.
    • Depth First Search (DFS)
    • Uses a stack data structure.
  • Both BFS and DFS can be implemented recursively or iteratively.
  • ST Path Problem: Determining if a path exists between two nodes (source and target) using either BFS or DFS with an additional check for the target node during traversal.

Maze Representation as Graph

  • A maze can be treated as a graph with:
    • Source Node (s): Start point of navigation.
    • Target Node (t): End point of navigation.
    • Walls (hash #): Impassable barriers.
    • Valid Paths (dot .): Passable areas where movement is allowed.
  • Different movement restrictions possible:
    • Right and down only.
    • Four cardinal directions (up, down, left, right).
    • Diagonal movement allowed.
  • Key Idea: Use BFS or DFS to find a path from s to t.
Graphical Representation
  • Use coordinates to represent nodes in a 2D space (e.g., using a vector of vectors).
  • Start BFS from coordinate (0, 0) and mark each node as visited.
  • An approach without needing to convert the maze directly into a graph.
Marking Mechanism
  • Using a boolean vector of vectors for visited nodes.
  • Another approach involves using a set to keep track of visited nodes.
Finding Neighbors
  • Neighbors identified via coordinate arithmetic based on allowed movements:
    • Up: (x-1, y)
    • Down: (x+1, y)
    • Right: (x, y+1)
    • Left: (x, y-1)
    • For diagonal: adjust x and y accordingly.
  • Ensure new coordinates are within maze bounds and not walls.
Handling Adjacent Nodes
  • Iterate through potential moves based on neighbor vectors, checking bounds and obstacles:
    • For each valid position, add it to the queue and mark it as visited.
    • Continue the process until you either find the target or exhaust all options.

Shortest Path in a Maze Using BFS

  • BFS guarantees the shortest path when graph is unweighted:
    • Each level explored represents a step away from the source.
  • Path Length Calculation:
    • Use a corresponding queue to keep track of cumulative path length as nodes are added.

Shortest ST Path Problem (Next Module Focus)

  • Transitioning to shortest path problems in more complex graphs (Dijkstra's algorithm):
    • Discussed Dijkstra's algorithm:
    • Use Case: Compute shortest path between a source node and any other node in a graph.
    • Requirements: Works on directed graphs and undirected graphs but no negative weights allowed.
    • Path representation using predecessors for backtracking the route.
    • Bellman-Ford Algorithm: Allows for negative weights but not negative weight cycles.
    • Floyd-Warshall: Computes shortest paths between all pairs of vertices.
    • A* Search: Heuristic-based algorithm for pathfinding but not covered in the course.

Implementation and Example Walkthroughs

  • Upcoming sessions will involve practical application of algorithms (e.g., Dijkstra).
  • Focus on worked examples rather than writing code directly.
  • Importance of understanding theoretical underpinnings and how to apply them to algorithmic problems.