Graphs record relationships. Nodes are connected to one another by edges. In a directed graph, the order of nodes connected by edges is not interchangeable, but rather they are ordered pairs. If a graph does not specify direction, we assume that it is not directed. Examples of graphs in real life include computer networks, social networks, transportation networks, information networks like the world wide web, and dependency networks which capture the inter-dependencies between components of a system(ie: a food web in nature). In non directed graphs, a path is a sequence of connected nodes. Simple paths contain no repetition of vertices. Cycles are like paths but the first node must be the same as the last and there can be no repetitions. An undirected graph is connected if there is a path between each pair of nodes. It is strongly connected if there is a path between each pair of nodes in both “directions”. Distance between two nodes is the number of nodes in the shortest path between them. A graph is a tree if it is connected and does not contain a cycle. Review: one node in a tree(often the smallest, no parents) is the root, descendants of nodes are children and nodes with children are their parents. Trees imply the concept of hierarchy. Each tree has exactly n-1 edges where n is the number of nodes. This is because the root has no edges and each addition adds one node and only one additional edge. Overall, this section is a solid 8/10. Very nice read.

The s-t connectivity problem us finding if there is a path between nodes s and t in a graph. This challenge resembles solving a maze. One approach to finding a solution is breadth first search. In breadth first search, we start at a “root” node s. We then search all nodes connected to it (first layer). Then, we search all nodes connected to those nodes in the first layer(second layer). We repeat until there are no nodes remaining. The number of a layer Li corresponds to its path distance from s. Because they are in layers, searches correspond to a tree like structure called a breadth-first search tree. Only edges which connect to a new node are included in the tree(no two edges to the same node in the next layer). Nodes will not be searched if there is no path between them ans s. Thus, the set R of searched nodes is the connected component of the graph containing s. If t is in R, there is a path and vice versa. Another tactic for solving the problem is depth-first search. This is a recursive approach. For depth-first search, we start at s and then search one connected node a, then search a connected node of b, etc, until we reach a node without a connection to a non-searched node. Then, we backtrack until we find a node with unexplored edges. We must maintain a copy of the nodes which we can backtrack to. Depth first search ultimately produces the exact same connected component as breadth first search. However, its tree representation looks very different from breadth first as seen in class. This is called a depth-first search tree. If a pair of nodes (a, b) are directly connected in the breadth first search tree of a graph then one is the ancestor of the other in the corresponding depth first search tree. The connected components of two nodes in a graph are either identical or have no nodes in common. This property holds for all graphs. Thus, to find all connected components of a graph we could find one connected component R and then only find the connected components of nodes not in R. This section was interesting, complex and very well articulated by the book. I would give it a solid 8/10 for readability.

We use adjacency lists to represent graphs. We will treat nodes as n and edges as m, and compute run-time in terms of both n and m. We cannot say for sure if n or m is more significant, so we will treat them as equals. However, m⇐ n^2 always. For both breadth and depth search, we aim for O(n+m) time. An alternative representation is the adjacency matrix(constant access, O(n^2) space. Adjacency list: array of nodes with corresponding linked lists of connected edges for each node. Just O(n+m) space rather than O(n^2). Since the order of nodes is crucial, queues and stacks are ideal data structures to represent them. In BFS, nodes are organized using a queue while in DFS, nodes are organized using a stack(recursive). Finding the set of all connected components is still O(n+m) for both techniques. This section was harder to follow: 6.5/10.

Bipartite Graphs cannot have nodes in the same layer connect→ strategy: color each layer red or blue and if any edge has the same color on both ends the graph is not bipartite. These are “forward graphs”. If a graph is bipartite then it cannot contain an odd cycle. Algorithm: perform breadth first search to add colors. Then, after this step, scan through the resulting tree to see if condition is met. Unsurprisingly, the total running time of this algorithm is O(n+m).

Directed graphs are one directional: edges must go from node a to node b and cannot go back from node b to node a. We still use adjacency lists for directed graphs but maintain two lists of edges: a to list and a from list. Searching is basically the same(time, techniques, etc) as in non-directed graphs, but must only follow nodes according to inherent direction. If a directed graph is strongly connected, every pair of nodes a and b must have paths between them (path from a to b and from b to a). Not always the case here. This has transitive properties: if a and b are mutually reachable, nodes b and c are mutually reachable, a and c must also be mutually reachable. This allows us to conclude that “strong components” of graphs are either identical or completely different(disjoint).

A directed acyclic graph is a directed graph with no cycles. The structure of these is often much richer than non-directed graphs without cycles(more edges). These DAGS are naturally ordered and usually applied to systems such as college courses where one cannot backtrack directly. The comparative classification of nodes in a DAG is called a “topological ordering”. In a topological ordering, all edges must “point forward”. If a graph has a topological ordering than it is a DAG. Further, is a graph is a DAG than it must have a topological ordering. The lowest node of any DAG has no incoming edges. There can also be other nodes with no incoming edges. Computing a topological ordering for a DAG takes O(n^2) time but may take O(n+m) only for very thin, non-dense graphs.