Chapter 3

• Graph: encodes pairwise relationships among a set of objects; consists of a collection V of nodes and a collection E of edges
• Directed Graph: consists of a set of nodes V and a set of directed edges E' (each e' is an ordered pair - u (tail) and v (head) are not interchangeable)

Graph Examples:

• Transportation Networks: airport nodes, flight path edges
• Communication Networks: connection of computers
• Information Networks: World Wide Web and links to various pages
• Social Networks: people nodes, friendships edges
• Dependency Networks: interdependencies among a collection of objects (i.e.-course offerings w/prerequisites

Paths and Connectivity:

• Simple Path: all vertices are distinct from one another
• Cycle: the sequence of nodes “cycles back to where it begins
• Directed Path/Cycle: the sequence of nodes in the path or cycle must respect the directionality of edges
• Connected Undirected Graph: for every pair of nodes u and v, there is a path from u to v
• Strongly Connected Directed Graph: for every two nodes, there is a path in both directions
• Short Path: route with as few “hops” as possible

Trees:

• Connected undirected graph that does not have a cycle
• w is a descendant of v if v lies on the path from the root to w
• x is a leaf if it has no descendants
• Hierarchical
• Every n-node tree has exactly n-1 edges
• Any two of the following statements implies the third
  1. G is connected
  2. G does not contain a cycle
  3. G has n-1 edges

This section was pretty simple, as it reviewed past concepts that were taught in multiple other classes. I like to have examples for applications of the various structures, so I appreciated the graph examples listed in this section. I think this section set a good foundation for working with graphs and trees. Readability: 10 Interesting: 8

Breadth-First Search

• add nodes one “layer” at a time
• start with s, include all nodes that are joined to s by an edge
  • Therefore, L_j+1 consists of all nodes that do not belong to an earlier layer and that have an edge to a node in layer L_j
• For each j >= 1, layer L_j produced by BFS consists of all nodes at distance exactly j from s. There is a path from s to t if and only if t appears in the same layer.
• Produces a tree rooted at s on the set of nodes reachable from s.

 BFS Execution:
   - Starting from node 1, Layer L<sub>1</sub> consists of the nodes {2,3}
   - Layer L<sub>2</sub> is then grown by considering the nodes in layer L<sub>1</sub> in order.For each node, the incident edges are examined. If an edge connects to a node that has already been discovered, it isn't added to the BFS.
   - Consider the nodes in the next layer in order. 
   - When no new nodes are left to be discovered, the algorithm terminates.