I. In-Class Exercises

Programming Exercises

1. Determine Whether a Graph Is Connected: L3331

II. Knowledge Summary

Core Idea

In graph theory, connectivity describes whether paths exist between vertices.

The exact meaning depends on whether the graph is directed or undirected.

Path-Related Terms

• Walk: alternating sequence of vertices and edges
• Trail: a walk with no repeated edges
• Simple path: a trail with no repeated vertices except possibly start and end
• Circuit: a trail whose start and end are the same
• Cycle: a simple path whose start and end are the same

Connectivity in Undirected Graphs

• Connected graph: every pair of vertices has a path between them
• Disconnected graph: at least one pair has no path
• Connected component: a maximal connected subgraph

Connectivity in Directed Graphs

• Strongly connected graph: every pair of vertices can reach each other in both directions
• Weakly connected graph: if edge directions are ignored, the graph becomes connected
• Strongly connected component: a maximal strongly connected subgraph

Execution Example

Undirected graph:

0 -- 1 -- 2     3 -- 4
                  |
                  5

Run DFS from 0:

• visit 0
• then 1
• then 2

Visited becomes: [true, true, true, false, false, false]

So the graph is not connected.

Run DFS from 3:

• visit 3, 4, 5

Therefore there are 2 connected components:

• {0, 1, 2}
• {3, 4, 5}

Directed example:

0 -> 1
^    |
|    v
3 <- 2

This graph is strongly connected.

If edge (3,0) is removed, it is no longer strongly connected, but it is still weakly connected.

Problem-Solving Steps

For "is an undirected graph connected?":

1. Build the graph
2. Run DFS or BFS from any vertex, such as 0
3. Mark all reachable vertices
4. If every vertex is visited, the graph is connected

Code Outline

1void dfs(int v, vector<vector<int>>& adj, vector<bool>& visited) {
2    visited[v] = true;
3    for (int u : adj[v]) {
4        if (!visited[u]) dfs(u, adj, visited);
5    }
6}

Common Mistakes

• Doing only one DFS when the goal is to count connected components
• Mixing up strong and weak connectivity
• Using undirected logic directly on directed graphs
• Forgetting to initialize visited
• Ignoring isolated vertices

III. Homework

Programming Exercises

1. Burning CDs: L3332