A graph consists of a collection V of nodes (or vertex) and a collection E of edges, each of which joins two of the nodes. Edges indicate a symmetric relationship between their ends in an undirected graph , and indicate an asymmetric relationships in a directed graph.
Path in an undirected graph G = (V,E) is 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.
An undirected graph is connected if, for every pair of nodes u and v, there's a path from u to v. The distance between u and v is the minimum number of edges in a u-v path
An undirected graph is a tree if it's connected and doesn't contain a cycle. Every n-node tree has exactly n-1 edges.
s-t connectivity: Find a path from s to t in the graph
The connected component of G containing s is the set of nodes that are reachable from the starting node s, BFS is one possible way to produce that component
To find this connected component, we define R = s. While we find an edge (u,v) where u ∈ R and $v \not\in R$, add v to R
The general algorithm to grow R is underspecified. Breath-First Search and Depth-First Search are 2 natural ways of ordering the nodes we visit
For each j ≥ 1, layer $L_j$ produced by breath-first search consist of all nodes at distance exactly j form s. There's a path from s to t if and only if t appers in some layer.
Let T be a breath-frist 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
visited = set()
def bfs(node):
visited.add(node)
for v in node.neighbors:
if v not in visited:
bfs(node)
For a given recursive call bfs(node) , all nodes that are marked "visited" between the invocation and the end of the recursive call are descendants of the given node in T
Let T be a depth-first search tree, where x and y be nodes in T. 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 2 nodes s and t in a graph, their connected components are either identical or disjoint