Graphs
Definition
Vertices and edges
Directed & undirected
One with arrows
One with plain lines
Applications
Adjacency matricies
To show all vertices adjacent to a given vertex.
Adjacency lists
Array of lists
Comparing runtime
Graph density
Can be dense or sparse.
Graph traversals
bfs and dfs
marked & unmarked states.
White -> grey -> black
Breadth first search
method
using a queue
runtime
Depth first search
method
using a stack (lifo)
recursive
runtime