graphs

It leads nowhere, making G a singleton node component.

It explores as deeply as possible before backtracking.

Breadth First Search (BFS).

O((n + m)²).

O(n + m).

Two vertices u and v are in the same component if there is a directed path from u to v and from v to u.

The presence of odd cycles.

Nodes at level i are colored 0 if i is even and 1 if i is odd.

All nodes at distance exactly j from the starting node s.

G, H, J, I, B, F, C, A, D, E.

It proves that the graph has no cycles.

It uses a stack to keep track of nodes to explore.

By removing each vertex in turn and checking if the graph remains connected using DFS or BFS.

A sequence of vertices where each pair is connected by an edge.

A tree.

Hopcroft and Tarjan in the 1970s.

All neighbors of s must be colored 1, making them the nodes of level 1.

Its vertex set V can be partitioned into sets X and Y such that every edge has one end in X and the other in Y.

A graph is represented as G = (V, E), where V is the vertex set and E is the edge set.

The root is an articulation point if it has more than one child.

It helps demonstrate the properties of strongly connected components.

Unreachable nodes that can be eliminated.

Level 0.

By performing a post-order traversal of the DFS tree.

Any DFS forest of it contains no back edges.

The set of all nodes reachable from a start node s.

The recursive call at v finishes before the call at x, confirming that v is a descendant of x.

O(m + n), where m is the number of edges and n is the number of vertices.

Graphs are useful models for reasoning about relations among objects and networked systems.

By checking if t belongs to the set R discovered by BFS.

An array of header cells pointing to linked lists of all vertices adjacent to each vertex.

Each connected component is a tree.

An ordering of nodes in a graph such that for every edge (v_i, v_j), i < j.

Memory objects accessible by the program.

Nodes not yet encountered that have an edge to some node in level L(i).

It is deleted along with its outgoing edges.

All edges are directed from higher finish time to smaller finish time.

If u is the parent of w, then w is called a child of u.

It must also imply that there is a path from x to v, completing the proof of their connectivity.

A tree-like structure called the BFS tree of G.

A set of vertices (nodes) and a set of edges.

Depth First Search (DFS).

O(m + n), where n = |V| and m = |E|.

The DFS tree looks very different from the BFS tree.

They connect the nodes of DFS in significant ways.

If it has a child w with low(w) ≥ Num(v).

If v is an articulation point, then the low() value for all explored nodes is ≥ Num(v).

I and J.

{A, C, F}.

Both end with singleton components.

To show that each tree found is a strongly connected component.

A directed graph without cycles, commonly used in computer science.

As a directed graph where jobs are nodes and precedence relations are directed edges.

Then G is a Directed Acyclic Graph (DAG).

It backtracks to the nearest node with unexplored neighbors.

(n 2) edges.

Mark the starting node as explored and add it to the result.

A node from which exit is unreachable.

It recursively calls DFS on each unexplored neighbor.

It checks if the node has been explored; if not, it marks it as explored.

All unexplored neighbors of the current node.

By using markers to keep track of visited nodes.

A bi-connected graph requires the deletion of at least two nodes to disconnect it, meaning no single node's removal can disconnect the graph.

Proof by contradiction.

There cannot be a back edge in a DFS of G, as a back edge would create a cycle.

It implies that any two nodes v and w in tree T can be reached from one another through paths involving the root x.

To output each subtree found as a strongly connected component (SCC) and remove it from the graph.

One of x or y is an ancestor of the other.

If (x, y) is an edge of G, then |i - j| ≤ 1.

The degree equals the number of neighbors.

O(|E|) space, since each directed edge is stored just once.

An articulation point is a node whose removal disconnects the graph.

Find a vertex with zero in-degree.

An underlying graph that is connected, but the directed graph may not have directed paths between all pairs.

Node v is a descendant of x in tree T, indicating a directed path from x to v in the reverse graph G R.

Pick any arbitrary vertex s and color it 0.

Their connected components are either identical or disjoint.

O(m + n).

Out-degree and in-degree.

It checks for bi-connectivity and finds all bi-connected components of a graph in O(n + m) time.

A path with no repeated vertices, except the first and last can be the same (forming a cycle).

n - 1 edges.

If x has a larger finish time than v, it indicates that v is a descendant of x in the DFS of graph G.

Whether the endpoints of each edge of G are colored differently.

Using colors red and blue (or 0 and 1).

The connected component of G containing s.

A 2-dimensional array V × V where A[u, v] = 1 for an edge (u, v).

Num(v) for the visit order and low(v) for the lowest-numbered vertex reachable from v.

Depth-First Search (DFS).

O(|V| + |E|).

1. Perform a DFS on G. 2. Number vertices in post-order. 3. Construct the reverse graph G R. 4. Perform a second DFS on G R starting from the highest numbered vertex.

It indicates the presence of an odd cycle.

If s appears in some level of BFS from s.

It joins two nodes u and v.

Proper application of graph theory ideas can drastically reduce the solution time for important problems.

low(v) is the minimum of Num(v), the lowest Num(w) among back edges (u, w), and the smallest low(w) among all children w of v.

There is a path between any two vertices.

Determining if there is a path joining two nodes s and t in a graph.

By using BFS to either discover the sets X and Y or detect an odd cycle.

All nodes that are descendants of u in the DFS tree T.

In a directed graph, the pair (u, v) is distinct from (v, u); in an undirected graph, they are the same.

An edge with both endpoints being the same.

It takes |V|² space even if the graph has very few edges.

If (u, v) is an edge, then v is adjacent to (or a neighbor of) u.

The World Wide Web, where web pages are nodes and hyperlinks are edges.

Nodes are computers and edges are physical links.

It consists of all neighbors of the starting node s.

It leads to the existence of a cycle.

A directed graph where there is a directed path between any two vertices.

A triangle is not bipartite because any partition will contain two nodes on the same side with an edge between them.

It can be assumed that G is connected; otherwise, the algorithm can be applied to each connected component separately.

The edge is not added to T because y was discovered during the recursive call.

By duplicating edges and orienting them both ways.

The map of routes served by an airline carrier, where nodes are airports and edges represent non-stop flights.

Traversing a sequence of nodes (and edges).