Recall from Chapter 1 that a graph G is simply a way of encoding pariwise relationships among a set of objects: it consists of a collection V of nodes and a collection E of edges, each of which “joins” two of the nodes. We thus represent an edge e ∈ E as a two-element subset of V: e = {u,v} for some u,v ∈ V, where we call u and v the ends of e. Edges indicated a symmetric relationsihp between their ends. WE use a directed graph when we want to show asymmetric relationships. A directed graph G' consists of a set of nodes V and a set of directed edges E'. Each e' ∈ E' is an ordered pair (u,v). We call u the tail of the edge and v the head. We also say that the edge leaves node u and enters node v. By default, graph will mean an undirected graph. Two notes: an edge should be written as a set of nodes {u,v}, but will frequently be written as (u,v); a node is often called a vertex.

We define a path in an undirected graph G = (V,E) to be a sequence P of nodes v_1, v_2, …, v_(k-1), v_k with the property that each consecutive pair v_i, v_(i+1) is joined by an edge in G. P is often called a path from v_1 to v_k, or a v_1 - v_k path. A path is called simple if all its vertices are distinct from one another. A cycle is a path v_1, v_2, …, v_(k-1), v_k, in which k > 2, the first k - 1 nodes are all distinct and v_1 = v_k (it “cycles” back to where it began).

All of these definitions carry over naturally to directed graphs with the following change: in a directed path or cycle, each pair of consecutive nodes has the property that (v_i, v_(i+1)) is an edge. In other words, the sequence of nodes in the path or cycle must respect the directionality of edges.

We say that an undirected graph is connected if, for every pair of nodes u and v, there is a path from u to v. We say a directed graph is strongly connected if, for every two nodes u and v, there is a path from u to v and a path from v to u. In addition to simply knowing about the existence of a path between some pair of nodes u and v, we may also want to know whether there is a short path. Thus we define the distance between two nodes u and v to be the minimum number of edges in a u-v path.

We say that an undirected graph is a tree if it is connected and does not contain a cycle. For thinking about the structure of a tree T, it is useful to root it at a particular node r. We “orient” each edge of T away from r; for each other node v, we declare the parent of v to be the node u that directly precedes v on its path from r; we decalre w to be a child of v if v is the parent of w. More generally, we say that w is a descendant of v if v lies on the path from the root to w; and we say that a node x is a leaf if it has no descendants.

• Every n-node tree has exactly n - 1 edges.
• Let G be an undirected graph on n nodes. Any two of the following statements implies the third.
  • G is connected.
  • G does not contain a cycle.
  • G has n - 1 edges.

Suppose we are given a graph G = (V,E) and two particular nodes s and t. We'd like to find an efficient algorithm that answers the question: Is there a path from s to t in G? → teh problem of determining s-t connectivity.

In this section, we describe two algorithms for this problem - BFS and DFS.

BFS is when we explore outward from s in all possible directions, adding nodes one “layer” at a time. Thus, we start with s and include all nodes that are joined by an edge to s (first layer). We then include all additional nodes that are joined by an edge to any node in the first layer (second layer). We continue until no new nodes are encountered. Layer L_1 consists of all nodes that are neighbors of s. Assuming that we have defined layers L_1,…,L_j, then layer 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. (Layer j is the set of all nodes at distance exactly j from s.) A node fails to appear in any of the layers iff there is no path to it. Thus, BFS is also computing shortest paths to them. It also produces a tree T rooted at s on the set of nodes reachable from s.

• Let T be a bfs search tree, let x and y be nodes in T belonging to layers L_i and L_j respectively and let (x,y) be an edge of G. Then i and j differ by at most 1.

The set of nodes discovered by the BFS algorithm is precisely those reachable from the starting node s. We will refer to this set R as the connected component of G containing s. Once we know that the c.c. containing s, we can simply check whether t belongs to it so as to answer the question of s-t connectivity.

• R will consist of nodes to which s has a path
• Initially R = {s}
• While there is an edge (u,v) where u ∈ R and v ∉ R
  • Add v to R
• Endwhile

Key property of algorithm: The set R produced at the end is precisely the c.c. of G containing s.

DFS explores G by going as deeply as possible and only retreating when necessary. DFS(u):

• Mark u as “explored” and add u to R
• For each edge (u,v) incident to u
  • If v is not marked “explored” then
    • Recursively invoke DFS(v)
  • Endif
• Endfor

To apply this to s-t connectivity, we simply declare all nodes initially to be not explored and invoke DFS(s).

DFS brings about a different tree than BFS. (look at exs. in book)

• Let T be a dfs tree, let x and y be nodes in T and let (x,y) be an edge of G that is not an edge of T. Then one of x or y is an ancestor of the other.

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

BFS and DFS