☕ DSA Java Articles

Topics › Graphs › Learning

Introduction to Graph

Easy TUF ID 1222 A2Z

Java source ↗ Edit this article ↗

What this covers

A graph is the most general way to describe “things” and “connections between things”. Arrays connect each element to the next one, trees connect each node to its children, and a graph drops every such restriction: any vertex may connect to any other. That generality is why so many problems become graph problems once you spot them: cities and roads, people and friendships, web pages and links, courses and prerequisites, cells of a grid and their neighbours.

This article fixes the vocabulary that every later graph problem uses: vertices and edges, directed and undirected graphs, degree, paths, cycles, weights, connectivity and trees. To keep the focus on ideas rather than data structures, every snippet here works on the simplest possible representation, a plain edge list. The next two articles introduce the adjacency matrix and adjacency list that real algorithms use. Each snippet is a method in the Java file, and main checks them on small hand-made graphs.

Vertices and edges

A graph G = (V, E) is a set of vertices (also called nodes) and a set of edges, each edge joining two vertices. In code, vertices are almost always numbered 0..n-1 (LeetCode style) or 1..n (most competitive programming input), and an edge is a pair of vertex numbers. An edge list is then just an int[][] where each row is {u, v}.

Here is the undirected graph used throughout this article, with five vertices and five edges 0-1, 0-2, 1-2, 1-3, 3-4:

0 ----- 1 ----- 3 ----- 4
 \     /
  \   /
   \ /
    2

Two vertices joined by an edge are adjacent, and each is a neighbour of the other. Nothing says a graph must be in one piece, that every vertex must have an edge, or that the vertices have any geometric position. The drawing is only a picture of the pairs.

Undirected and directed graphs

In an undirected graph an edge {u, v} can be walked both ways: friendship is mutual, a two-way road connects both ends. In a directed graph (a digraph) each edge is an arrow u -> v that can be followed only from u to v: a one-way street, “page u links to page v”, “course u must come before course v”. A directed edge is often called an arc.

The same edge list can mean either kind of graph; the difference lies entirely in how you read it. That is why the methods below take a boolean directed flag. A directed graph can still have both u -> v and v -> u, and an undirected graph is effectively a directed one in which every arrow comes with its reverse. That second view is how adjacency lists store undirected graphs later on: every undirected edge is added twice.

Degree and the handshake lemma

The degree of a vertex in an undirected graph is the number of edges touching it. Counting is a single pass over the edge list: each edge {u, v} adds one to u and one to v.

static int[] degrees(int n, int[][] edges) {
    int[] deg = new int[n];
    for (int[] e : edges) {
        deg[e[0]]++;
        deg[e[1]]++;
    }
    return deg;
}

For the example graph the degrees are [2, 3, 2, 2, 1]. Their sum is 10, exactly twice the number of edges. This is no coincidence: every edge contributes exactly 2 to the total, one for each end. This is the handshake lemma, sum of degrees = 2E. A useful corollary is that the number of vertices with odd degree is always even (here vertices 1 and 4), because an odd count of odd numbers could not add up to an even total.

In a directed graph each arrow leaves one vertex and enters another, so a vertex has an out-degree (arrows leaving) and an in-degree (arrows entering):

static int[][] inOutDegrees(int n, int[][] edges) {
    int[] in = new int[n], out = new int[n];
    for (int[] e : edges) {
        out[e[0]]++;
        in[e[1]]++;
    }
    return new int[][]{in, out};
}

For the directed graph 0->1, 1->2, 2->0, 2->3, the in-degrees are [1, 1, 1, 1] and the out-degrees are [1, 1, 2, 0]. Each sum is E = 4, the directed version of the handshake lemma. Vertices with in-degree zero (sources) and out-degree zero (sinks, like vertex 3 here) matter a great deal later in topological sorting.

Paths and cycles

A path is a sequence of vertices in which each consecutive pair is joined by an edge and no vertex repeats. To check one we need to ask “is there an edge from a to b?”, which on an edge list means scanning all edges:

static boolean hasEdge(int[][] edges, int u, int v, boolean directed) {
    for (int[] e : edges) {
        if (e[0] == u && e[1] == v) return true;
        if (!directed && e[0] == v && e[1] == u) return true;
    }
    return false;
}

static boolean isPath(int n, int[][] edges, int[] seq, boolean directed) {
    if (seq.length == 0) return false;
    boolean[] used = new boolean[n];
    for (int i = 0; i < seq.length; i++) {
        if (used[seq[i]]) return false;                       // a path never revisits a vertex
        used[seq[i]] = true;
        if (i > 0 && !hasEdge(edges, seq[i - 1], seq[i], directed)) return false;
    }
    return true;
}

static boolean isCycle(int n, int[][] edges, int[] seq, boolean directed) {
    int k = seq.length;
    if (k < (directed ? 1 : 3)) return false;                 // undirected u-v-u would reuse one edge
    if (!isPath(n, edges, seq, directed)) return false;
    return hasEdge(edges, seq[k - 1], seq[0], directed);      // the closing edge
}

0-1-3-4 is a path in the example graph, and so is 4-3-1-2-0, which happens to use every vertex. 0-3 is not, because 0 and 3 are not adjacent, and 0-1-2-0 is not a path because it returns to 0.

A cycle is a path that ends next to where it started: after the last vertex there is an edge back to the first. In the example, 0-1-2 is a cycle (a triangle), and so is 2-1-0, the same triangle walked the other way. 1-3-4 is not, because 4 has no edge back to 1.

Look at the minimum length in isCycle. In an undirected graph, 0-1 followed by “back to 0” would walk the single edge 0-1 there and back, which is not a cycle in any useful sense, so an undirected cycle needs at least three distinct vertices. In a directed graph the arrows 0->1 and 1->0 are two different edges, so 0->1->0 is a genuine cycle of length 2, and a self-loop 0->0 is a cycle of length 1. This exact distinction comes back in the cycle detection problems, where an undirected search must ignore the edge it just arrived by, while a directed search must not.

Direction also changes which sequences count. In the directed graph above, 0->1->2 is a cycle because the arrow 2->0 exists, but 0, 2, 1 is not, because there is no arrow 0->2. Read as undirected, 0-2-1 is a perfectly good triangle. A graph with no cycles at all is acyclic; a directed acyclic graph (DAG) is the structure behind dependency and scheduling problems.

Weighted graphs

Often an edge carries a number: the length of a road, the price of a flight, the time a task takes. The graph is then weighted, and an edge is a triple {u, v, w}. An unweighted graph behaves like a weighted one where every weight is 1. The weight of a path is the sum of its edge weights:

static long pathWeight(int[][] wEdges, int[] seq, boolean directed) {
    long total = 0;
    for (int i = 1; i < seq.length; i++) {
        long best = Long.MAX_VALUE;
        for (int[] e : wEdges) {
            boolean forward = e[0] == seq[i - 1] && e[1] == seq[i];
            boolean backward = !directed && e[0] == seq[i] && e[1] == seq[i - 1];
            if (forward || backward) best = Math.min(best, e[2]);
        }
        if (best == Long.MAX_VALUE) return -1;                // consecutive vertices are not adjacent
        total += best;
    }
    return total;
}

With edges 0-1 (4), 1-2 (1), 0-2 (7), 2-3 (3), the path 0-1-2-3 weighs 4 + 1 + 3 = 8, while 0-2-3 weighs 7 + 3 = 10 despite using fewer edges. That gap between “fewest edges” and “least total weight” is the whole reason shortest-path algorithms such as Dijkstra exist: plain BFS minimises edge count, not weight. The method returns long because summing many int weights can overflow, and it takes the cheapest edge when two vertices are joined by several parallel edges.

How many edges can a graph have?

A simple graph has no self-loops and no two edges between the same pair. With n vertices there are n(n-1) ordered pairs of distinct vertices, so a directed simple graph has at most n(n-1) edges and an undirected one at most half that:

static long maxEdges(int n, boolean directed) {
    long pairs = (long) n * (n - 1);                          // long: n = 10^5 already overflows int
    return directed ? pairs : pairs / 2;
}

Five vertices allow at most 10 undirected edges, and 100000 vertices allow almost 5 * 10^9, which no longer fits in an int. A graph with close to the maximum is dense; one with E on the order of V is sparse. Most input graphs in practice are sparse, and that single fact decides which representation to use in the next article.

Connected graphs and trees

An undirected graph is connected when every vertex can reach every other one along some path. If it is not, it falls apart into connected components, the maximal pieces that are connected internally. The method below checks connectivity using only the edge list: mark vertex 0 as reached, then keep sweeping the edges, marking the far end of any edge with one end reached, until a sweep changes nothing.

static boolean isConnected(int n, int[][] edges) {
    if (n == 0) return true;
    boolean[] reached = new boolean[n];
    reached[0] = true;
    boolean changed = true;
    while (changed) {
        changed = false;
        for (int[] e : edges) {
            if (reached[e[0]] != reached[e[1]]) {             // one end reached, the other not yet
                reached[e[0]] = true;
                reached[e[1]] = true;
                changed = true;
            }
        }
    }
    for (boolean r : reached) if (!r) return false;
    return true;
}

static boolean isTree(int n, int[][] edges) {
    return n >= 1 && edges.length == n - 1 && isConnected(n, edges);
}

The sweep is slow, O(V * E) in the worst case, and proper traversals (BFS and DFS) will do the same job in O(V + E). But it makes the definition concrete: reachability spreads along edges and nowhere else.

A tree is a connected graph with no cycle. Trees have a remarkable counting property: a tree on n vertices has exactly n - 1 edges, and any connected graph with n - 1 edges is a tree. Intuitively, connecting n vertices needs at least n - 1 edges, and any edge beyond what is needed must close a loop. The example graph is connected but has 5 edges on 5 vertices, so it must contain a cycle (the triangle). Drop the edge 1-2 and it becomes a tree. The binary trees you have met before are rooted trees where each node has at most two children; here a tree has no root and no left or right.

Note that n - 1 edges alone is not enough. The edges 0-1, 1-0, 2-3 on four vertices number three, but the duplicate wastes one and the graph is in two pieces. Both conditions, the edge count and connectivity, are needed.

Edge cases and pitfalls