This module provides depth-first search (DFS) and breadth-first search (BFS) traversal algorithms for graphs.
Functions
dfs
Performs depth-first traversal starting from a given vertex.
from dsa.graph_traversal import dfs
path = dfs(graph, vertex, visited=None, path=None, debug=False, stack=None)
Graph object with an adjacents(v) method that returns adjacent vertices
Set of visited vertices (used internally for recursion)
Traversal order result (used internally for recursion)
If True, prints internal state including current vertex, adjacents, stack, and visited set
Internal recursion stack (debug only)
List of vertices in DFS traversal order
from dsa.graph import AdjacencyListGraph
from dsa.graph_traversal import dfs
# Create a graph
graph = AdjacencyListGraph()
graph.add_edge("A", "B")
graph.add_edge("A", "C")
graph.add_edge("B", "D")
graph.add_edge("C", "E")
# Perform DFS traversal
path = dfs(graph, "A")
print(path) # Output: ['A', 'B', 'D', 'C', 'E']
dfs_path
Finds a path from start vertex to end vertex using depth-first search.
from dsa.graph_traversal import dfs_path
path = dfs_path(graph, start, end, visited=None)
Graph object with an adjacents(v) method
Set of visited vertices (used internally)
Path from start to end as a list of vertices, or None if no path exists
from dsa.graph import AdjacencyListGraph
from dsa.graph_traversal import dfs_path
graph = AdjacencyListGraph()
graph.add_edge("A", "B")
graph.add_edge("B", "C")
graph.add_edge("A", "D")
graph.add_edge("D", "C")
# Find a path from A to C
path = dfs_path(graph, "A", "C")
print(path) # Output: ['A', 'B', 'C'] or ['A', 'D', 'C']
bfs
Performs breadth-first traversal starting from a given vertex.
from dsa.graph_traversal import bfs
path = bfs(graph, start, debug=False)
Graph object with an adjacents(v) method
If True, prints internal state including current vertex, adjacents, and queue
List of vertices in BFS traversal order
from dsa.graph import AdjacencyListGraph
from dsa.graph_traversal import bfs
# Create a graph
graph = AdjacencyListGraph()
graph.add_edge("A", "B")
graph.add_edge("A", "C")
graph.add_edge("B", "D")
graph.add_edge("C", "E")
# Perform BFS traversal
path = bfs(graph, "A")
print(path) # Output: ['A', 'B', 'C', 'D', 'E']
bfs_path
Finds the shortest path from start vertex to end vertex using breadth-first search.
from dsa.graph_traversal import bfs_path
path = bfs_path(graph, start, end)
Graph object with an adjacents(v) method
Shortest path from start to end as a list of vertices, or None if no path exists
from dsa.graph import AdjacencyListGraph
from dsa.graph_traversal import bfs_path
graph = AdjacencyListGraph()
graph.add_edge("A", "B")
graph.add_edge("B", "C")
graph.add_edge("A", "D")
graph.add_edge("D", "E")
graph.add_edge("E", "C")
# Find shortest path from A to C
path = bfs_path(graph, "A", "C")
print(path) # Output: ['A', 'B', 'C']