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