Graph
representations
matrix
linked lists
digraphs
weighet graphs
vertices w/ "cost"
collection of points
nodes
vertices
G = (V . E)
Search algorithms
depth-first
breadth-first
use a stack to trace the operations
starts at an arbitrary vertex marking it as visited
proceeds to unvisited vertices until a dead end
goes back and try to visit anothers vertices and find others dead ends
visit all the vertices that are adjacent to a starting vertex
use a queue to trace operations
go as far from "home" it cans
one ordering
tree and cross edges
connectivity, acyclicity, minimum-edge paths
Θ(V²)
Θ(V+E)
two ordering
tree and back edges
connectivity, acyclicity, articulation points
Θ(V²)
Θ(V+E)
Topological Sorting ????