Chapter 3

*A graph is a way of encoding pairwise relationships among a set of objects
*Has a set of nodes and a set of edges connecting these nodes
*Directed and Undirected graphs

• Directed graphs have direction in there edges whereas undirected graphs do not
  

*Path - sequence of nodes joined by edges
*Graphs are connected if there is a path from every edge to every other edge
*Directed graphs are strongly connected if every edge has a path to every other edge
*A graph is a tree if it is connected and does not contain a cycle

*Two different ways to solve the “maze problem” - Depth First Search or Breadth First Search

• DFS - Select first edge leading out of first node, then select first edge leading out of the node that you are lead to and so on until you reach a dead end at which point u go back to the beginning. You are going as deep as possible before branching out
  
• BFS - Explore outward from the starting point adding nodes one “layer” at a time
  

*Two ways to represent graphs:

• Adjacency Matrix - like a table of all the nodes and the edges that connect them. If the edges are weighted then the value of the weight of the edge would be put in the place in the grid where the two nodes meet.
  
• Adjacency List - Essentially a list of lists, it has a list for each node of all the other nodes that this node connects to.
  

*Queue - First In First Out (FIFO) - data structure in which the first element that is added to the queue is the first one out. much like a line at the dining hall or cars waiting at a stop light
*Stack - Last In First Out (LIFO) - data structure in which the last element added to the stack is the first one removed. this is similar to a stack of plates. You only take the one thats on top or the last one added to it.
*For breadth first search it doesn't necessarily matter which data type you use although a queue works well
*A stack is optimal for depth first search

*Bipartite graph - a graph where the set of nodes can be split up into two sets of nodes where every edge in the graph has one end in set X and the other in set Y where no two edges in the same set are connected
*An algorithm for testing the bipartiteness of a graph is laid out on pages 95 and 96

*Represent a directed graph much like an undirected graph with an adjacency list except this time each node contains two lists. One list details the list of nodes the current node connects to and the other list has a list of nodes that have edges connecting into it.
*A directed graph is strongly connected if every pair of nodes in the graph is mutually reachable(there is a path between each pair of nodes where they can reach each other)

*If a directed graph contains no cycles it is a directed acyclic graph
*Topological ordering - in a topological ordering for a graph all edges point from left to right. If a graph has a topological ordering it is directed and acyclic
*An algorithm for computing topological ordering is specified on page 101

With yet another thrilling chapter of Algorithm Design in the books I can say confidently that while the material may not be too flashy or fun to read, it is a necessary evil as I find myself coming away with a much clearer picture of the class after reading each chapter. The readings are a great way to hammer in everything we've learned during the week just in time to use it on the homework assignments. This chapter in particular was a little easier to read, but also a little longer, than the other reading assignments.

Readability: 8/10