The most bestest of the data structures
SOOO many problems eventually become graph problems. And this is by far the largest section of algorithms.
First, lets just describe a graph
(whiteboard)
All trees are graphs, not all graphs are trees
Terminology of Graphs
This is not an exhaustive list of terms, but it is the terms that we may end up
using today.
Graph Terms
cycle: When you start at Node(x), follow the links, and end back at Node(x)
acyclic: A graph that contains no cycles
connected: When every node has a path to another node
directed: When there is a direction to the connections. Think Twitter
undirected: !directed. Think Facebook (i haven't been on in 10 years, it may have changed)
weighted: The edges have a weight associated with them. Think Maps
dag: Directed, acyclic graph.
Implementation Terms
node: a point or vertex on the graph
edge: the connection betxit two nodes
Big O
BigO is commonly stated in terms of V
and E
where V
stands for vertices
and E
stands for edges
So O(V * E)
means that we will check every vertex, and on every vertex we check
every edge
How are graphs represented
- adj list
- adj matrix (whiteboard)
Basic Searches
BFS and DFS still exist on a graph, and they are virtually no different than on a tree.
(whiteboard + complexity)
Lets implement these!
- BFS on Adj. Matrix
- DFS on Adj. List
Dijkstra's Shortest Path
- what is it?
- where is it used?
- variations of it (don't whiteboard yet)
Probably your first graph algo after BFS/DFS
- don't forget to say non negative weights
(whiteboard)
- running time