Types of Graph

A graph's type is not a label you memorize — it is a set of structural constraints on its edge relation (direction, weight, cycle-freedom, reachability) that determines which traversal invariants hold and therefore which algorithms are even valid to run on it. Classifying a graph correctly, before picking an algorithm, is what separates a working solution from an infinite loop or a wrong answer.

Recognize the pattern

• Problem says "one-way", "prerequisite", "must happen before" → directed edges.
• Problem gives a distance/cost/time on each connection → weighted.
• "Can you get back to where you started?" / "detect a loop" → cycle question, directed or undirected.
• "Is everything reachable?" on an undirected graph → connectivity; on a directed graph where you also need the return path → strong connectivity.
• "Order these tasks respecting dependencies" → needs a DAG (topological sort only exists if acyclic).

Brute force → optimal (determining the type)

Brute force cycle check: for every pair of vertices, enumerate all simple paths between them and see if any path returns to its start. This is exponential — a complete graph on V vertices has on the order of (V−2)! simple paths between any two fixed vertices, not V!, but it is still combinatorially explosive and unusable beyond tiny graphs.

Optimal: a single DFS with 3-color marking (white/gray/black) detects a cycle in one pass: a back-edge to a gray (currently-on-stack) node means a cycle exists. Connectivity and strong connectivity have the same brute-force-vs-optimal gap: brute force runs BFS/DFS from every vertex (O(V·(V+E))); the optimal approach for strong connectivity is Kosaraju's or Tarjan's algorithm, which finds all strongly connected components using a constant number of linear passes — a second DFS on the transpose graph (Kosaraju) or a single DFS maintaining a low-link array (Tarjan) — instead of restarting a traversal from every vertex.

Complexity, derived

DFS/BFS visits each vertex once and relaxes each edge once (undirected: twice, once per endpoint's adjacency list) → O(V+E) time, O(V) space for the visited/color array and recursion stack. Naive per-vertex traversal for connectivity repeats this V times → O(V·(V+E)). Kosaraju's SCC algorithm runs DFS twice (once for finish order, once on the transpose) — still two linear passes → O(V+E) total, O(V) extra space for the finish-order stack and component labels. Union-Find based cycle detection on an undirected graph processes E edges with near-constant find/union → O(E·α(V)), essentially linear.

Worked example: classifying with one DFS pass

Directed graph: edges A→B, B→C, C→A, C→D. DFS from A, colors start all WHITE.

Because a back edge to a GRAY node was found, this directed graph is cyclic — it is not a DAG, so no topological sort exists until the A→B→C→A cycle is broken.

Implementation

3-color DFS cycle detection (directed graph):

enum Color { WHITE, GRAY, BLACK }

boolean hasCycle(int v, Map<Integer, List<Integer>> adj, Color[] color) {
    color[v] = Color.GRAY;
    for (int u : adj.getOrDefault(v, List.of())) {
        if (color[u] == Color.GRAY) return true;        // back edge -> cycle
        if (color[u] == Color.WHITE && hasCycle(u, adj, color)) return true;
    }
    color[v] = Color.BLACK;
    return false;
}

Undirected cycle detection (visited + parent, self-loop aware):

boolean hasCycleUndirected(int v, int parent, Map<Integer, List<Integer>> adj, boolean[] visited) {
    visited[v] = true;
    for (int u : adj.getOrDefault(v, List.of())) {
        if (u == v) return true;                 // self-loop: trivial cycle of length 1
        if (!visited[u]) {
            if (hasCycleUndirected(u, v, adj, visited)) return true;
        } else if (u != parent) {
            return true;                          // back edge to a distinct, already-visited vertex
        }
    }
    return false;
}

Union-Find cycle detection (undirected):

int[] parent;
int find(int x) { return parent[x] == x ? x : (parent[x] = find(parent[x])); }
boolean union(int a, int b) {
    int ra = find(a), rb = find(b);
    if (ra == rb) return false;   // already in same set -> edge (a, b) would close a cycle
    parent[ra] = rb;
    return true;
}
// for each edge (a, b): if a == b it is a self-loop cycle; else if (!union(a, b)) a cycle is found

Kosaraju's SCC algorithm (two linear DFS passes):

void kosaraju(Map<Integer, List<Integer>> adj, int n) {
    boolean[] visited = new boolean[n];
    Deque<Integer> finishOrder = new ArrayDeque<>();
    for (int v = 0; v < n; v++) if (!visited[v]) fillOrder(v, adj, visited, finishOrder);

    Map<Integer, List<Integer>> transposed = transpose(adj, n);
    Arrays.fill(visited, false);
    List<List<Integer>> sccs = new ArrayList<>();
    while (!finishOrder.isEmpty()) {
        int v = finishOrder.pop();
        if (!visited[v]) {
            List<Integer> component = new ArrayList<>();
            collect(v, transposed, visited, component);   // fillOrder / collect are standard DFS helpers
            sccs.add(component);
        }
    }
}

Pitfalls

• Detecting a cycle in a directed graph with plain visited/unvisited (2-color) instead of 3-color (white/gray/black) — a cross edge to an already-finished node is mistaken for a cycle, giving false positives.
• Applying undirected connectivity logic (single BFS/DFS reaches everyone → connected) to a directed graph — that only proves weak connectivity, not strong connectivity.
• A self-loop (an edge v–v) is a valid cycle in an undirected graph — a trivial cycle of length 1 — and standard DFS cycle detection correctly flags it, since the neighbor v is already visited and v is not equal to its own parent. What is not a cycle is a plain 2-vertex back-and-forth (A–B, walking the same edge back to the immediate parent); that case needs the parent check specifically because a true cycle among distinct vertices requires ≥3 of them — do not fold the self-loop case into that exclusion.
• Forgetting that a tree is only an undirected acyclic graph if it is also connected; disconnected acyclic pieces form a forest, not a tree.

When to use / when not, and trade-offs

Classify the graph before choosing storage and algorithm: a DAG signals topological sort / DP-on-DAG opportunities (longest path, task scheduling); a weighted graph signals Dijkstra/Bellman-Ford/Floyd-Warshall instead of plain BFS; an unweighted graph makes BFS sufficient and Dijkstra wasteful overkill. Representation trade-off: adjacency list (O(V+E) space) suits sparse graphs and is the default for most classifications above; adjacency matrix (O(V²) space) suits dense graphs or when O(1) edge-existence checks matter, e.g. checking if a specific edge exists for strongly-connected-graph queries. Don't reach for Tarjan/Kosaraju (O(V+E)) if you only need weak connectivity on an undirected graph — a single BFS/DFS already answers that in the same time with less code. Similarly, prefer Union-Find over a full DFS-based cycle check when edges arrive incrementally (e.g. Kruskal's MST) — it avoids re-traversing the graph on every insertion.

Takeaways

• Direction, weight, and cycle-freedom are independent axes — a graph can be directed, weighted, and cyclic all at once.
• Cycle detection needs 3 colors in directed graphs; in undirected graphs, visited/parent tracking suffices, and a self-loop is itself a trivial cycle — only the immediate-parent edge is excluded.
• Connectivity in directed graphs splits into weak (ignore direction) and strong (path both ways) — always confirm which one a problem means.
• Kosaraju's and Tarjan's algorithms find all SCCs using a small, constant number of linear-time DFS passes — not exactly "one pass", but still O(V+E) overall, which is what makes them optimal versus per-vertex brute force.

Recall: Why does 2-color (visited/unvisited) DFS cycle detection give false positives on a directed graph, and what does the 3rd color fix?

Synthesized from CLRS (Introduction to Algorithms) graph traversal chapters and standard competitive-programming graph taxonomy references.