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