dsa.graph_traversal module

dsa.graph_traversal.bfs(graph, start, debug=False)

Breadth-first traversal.

Parameters:

• graph – Graph object with an adjacents(v) method.

• start (str) – Starting vertex.

• debug (bool) – If True, print internal state.

Returns:

The vertices in BFS order.

Return type:

list

dsa.graph_traversal.bfs_path(graph, start, end)

Return the shortest path from start to end using BFS. If no path exists, return None.

Parameters:

• graph – Graph object with an adjacents(v) method.

• start (str) – Starting vertex.

• end (str) – Ending vertex.

Return type:

list | None

dsa.graph_traversal.dfs(graph, vertex, visited=None, path=None, debug=False, stack=None)

Depth-first traversal.

Parameters:

• graph – Graph object with an adjacents(v) method

• vertex (str) – Starting vertex

• visited (set) – Set of visited vertices

• path (list) – Traversal order result

• debug (bool) – If True, print internal state

• stack (list) – Internal recursion stack (debug only)

Return type:

list

dsa.graph_traversal.dfs_path(graph, start, end, visited=None)

Return a path from start to end using DFS, or None if not found.

Parameters:

• graph – Graph object with an adjacents(v) method.

• start (str) – Starting vertex.

• end (str) – Ending vertex.

• visited (set) – Set of visited vertices.

Returns:

Path from start to end if exists, else None.

Return type:

list or None