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 ????