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. 

Exploring a Connected Component

• R = {s}, where R is the connected component of G containing s
• Find an edge (u,v) where u is in R, but v is not. → Add v to r
• The set R produced at the end of the algorithm is precisely the connected component of G containing s.
• Note: algorithm is underspecified, no specific order for choosing edges

Depth-First Search

• Explores G by going as deeply as possible and only retreating when necessary.

• Start by declaring all nodes to be not explored
• For a given recursive call DFS(u), all nodes that are marked “Explored” between the invocation and end of this recursive call are descendants of u in T.

Similarities and Differences between DFS and BFS

1. Both build connected components containing s
2. Both create a natural rooted tree T on the component containing s
3. DFS typically visits the same set of nodes in a different order than BFS
4. DFS probes down long paths unlike, so the tree will have a very different structure than one from BFS
5. DFS tree is narrow and deep; BFS tree is short and bushy

The Set of All Connected Components

• For any two nodes s ant t in a graph, their connected components are either identical or disjoint

Representing Graphs

There are two basic ways to represent graphs:

1. Adjacency Matrix: nXn matrix
2. Adjacency List

• With at most one edge between any pair of nodes, the number of edges m can be at most (n choose 2) ⇐ n².
• Connected graphs: at least m >= n-1 edges

Advantages and disadvantages of Adjacency Matrix vs. List

1. The adjacency matrix representation of a graph requires O(n²) space, while the adjacency list representation requires only O(m+n) space.
2. Matrix: allows O(1) time to check if a given edge exists in the graph, but representation takes O(n²) space and checking for edges takes considerable O(n) time
3. List: works better for sparse graphs, there is an array containing a list of all nodes adjacent to node v, requires O(m+n) space, length of all lists in 2m → O(m)

• Degree of a node v is the number of incident edges it has

Queues and Stacks

• Order of element selection is crucial in DFS and BFS
• Queue: set from which we extract elements in FIFO order
• Stack: set from which we extract elements in LIFO order
• Use a doubly linked list as representations
  • Queue: new element is added to the end of the lists as the last element
  • Stack: new element is added to the first position
  • Insertions are O(1)

Implementing Breadth-First Search

• Use an adjacency list
• Array of Discovered nodes, length n

• Can use either a queue or stack in the below algorithm since order in each layer doesn't matter.

• This algorithm runs in O(m+n) time when using the adjacency list representation.
• Algorithm can be implemented using a single list L maintained as a queue; nodes are processed in the order they are first discovered, hence all nodes in a layer are processed as a contiguous sequence

Implementing Depth-First Search

• Nodes are processed in a stack, rather than in a queue.
• Explores a node u, scans neighbors of u, shifts attention to first not-yet explored node v, explores v
• Set array Explored[v] to be true when we scan v's incident edges
• Algorithm is underspecified: adjacency list of a node being explored can be processed in any order

• Have an array parent; set parent[v] = u when node v is added to stack; when node u (but not s) is marked as Explored, edge can be added to the tree
• Adding and deleting nodes from stack is O(1)
• Total number of nodes added to S: O(m+n)

Finding the Set of All Connected Components

• O(m+n): although algorithm may run BFS/DFS multiple times, only a constant amount of work on a given edge or node is done in the iteration when the connected component it belongs to is under consideration