Skip to main content

Documentation Index

Fetch the complete documentation index at: https://mintlify.com/ucxinstructor/dsa_package/llms.txt

Use this file to discover all available pages before exploring further.

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
Graph
required
Graph object with an adjacents(v) method that returns adjacent vertices
​
vertex
str
required
Starting vertex label
​
visited
set
default:"None"
Set of visited vertices (used internally for recursion)
​
path
list
default:"None"
Traversal order result (used internally for recursion)
​
debug
bool
default:"False"
If True, prints internal state including current vertex, adjacents, stack, and visited set
​
stack
list
default:"None"
Internal recursion stack (debug only)
​
path
list
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
Graph
required
Graph object with an adjacents(v) method
​
start
str
required
Starting vertex label
​
end
str
required
Ending vertex label
​
visited
set
default:"None"
Set of visited vertices (used internally)
​
path
list | None
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
Graph
required
Graph object with an adjacents(v) method
​
start
str
required
Starting vertex label
​
debug
bool
default:"False"
If True, prints internal state including current vertex, adjacents, and queue
​
path
list
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
Graph
required
Graph object with an adjacents(v) method
​
start
str
required
Starting vertex label
​
end
str
required
Ending vertex label
​
path
list | None
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']

Build docs developers (and LLMs) love

Get started for freeTalk to us