Graph transversal
course Algorithmics
last review @April 3, 2023
mastery rookie
assignment
progress not started
Weight
Files
date
due date
notes DFS and BFS
days left
Depth-first search:
The algorithm starts at a chosen "root" vertex and moves to adjacent, unvisited
vertices until it can no longer find unexplored vertices. Then it backtracks along
previously visited vertices until it finds a new path to uncharted territory. This process
repeats until it backtracks past the original "root" vertex from the first step. The DFS
algorithm runs on a Stack ADT.
G = graph, v = vertex in G
procedure DFS(G, v) is
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w ← G.adjacentVertex(v, e)
if vertex w is unexplored then
label e as a discovered edge
recursively call DFS(G, w)
else
label e as a back edge
Breath- first search:
Graph transversal 1
course Algorithmics
last review @April 3, 2023
mastery rookie
assignment
progress not started
Weight
Files
date
due date
notes DFS and BFS
days left
Depth-first search:
The algorithm starts at a chosen "root" vertex and moves to adjacent, unvisited
vertices until it can no longer find unexplored vertices. Then it backtracks along
previously visited vertices until it finds a new path to uncharted territory. This process
repeats until it backtracks past the original "root" vertex from the first step. The DFS
algorithm runs on a Stack ADT.
G = graph, v = vertex in G
procedure DFS(G, v) is
label v as explored
for all edges e in G.incidentEdges(v) do
if edge e is unexplored then
w ← G.adjacentVertex(v, e)
if vertex w is unexplored then
label e as a discovered edge
recursively call DFS(G, w)
else
label e as a back edge
Breath- first search:
Graph transversal 1
