Remove an Edge From a Directed Graph

Given a directed graph as an adjacency list and an edge u → v, remove that edge from the graph. Report whether the edge existed.

Example

graph LR
    subgraph before["before"]
        a0["0"] --> a1["1"]
        a0 --> a2["2"]
        a1 --> a3["3"]
        a2 --> a3
    end
    subgraph after["after removing 0 -> 2"]
        b0["0"] --> b1["1"]
        b1 --> b3["3"]
        b2["2"] --> b3
    end

Text

adj before: [[1, 2], [3], [3], []]
adj after:  [[1], [3], [3], []]

Brute force: rebuild the graph without the edge

Turn the adjacency list back into a list of edges, drop the one to remove, and build a new adjacency list.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static List<List<Integer>> removeEdge(List<List<Integer>> adj, int u, int v) {
        List<List<Integer>> rebuilt = new ArrayList<>();
        for (int i = 0; i < adj.size(); i++) rebuilt.add(new ArrayList<>());
        for (int from = 0; from < adj.size(); from++) {
            for (int to : adj.get(from)) {
                if (!(from == u && to == v)) {
                    rebuilt.get(from).add(to);
                }
            }
        }
        return rebuilt;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = List.of(List.of(1, 2), List.of(3), List.of(3), List.of());
        System.out.println(removeEdge(adj, 0, 2));
    }
}

Output

[[1], [3], [3], []]

Time: O(V + E). Space: O(V + E) for the new graph.

Optimal: edit only `adj.get(u)`

A directed edge u → v is stored in exactly one place: adj.get(u), an ArrayList<Integer>. Find v in that list and remove it. Nothing else changes.

Java

import java.util.ArrayList;
import java.util.List;

public class Main {
    static boolean removeEdge(List<List<Integer>> adj, int u, int v) {
        int i = adj.get(u).indexOf(v);
        if (i == -1) {
            return false;
        }
        adj.get(u).remove(i); // remove(int index) keeps the order of the remaining neighbors
        return true;
    }

    public static void main(String[] args) {
        List<List<Integer>> adj = new ArrayList<>();
        adj.add(new ArrayList<>(List.of(1, 2)));
        adj.add(new ArrayList<>(List.of(3)));
        adj.add(new ArrayList<>(List.of(3)));
        adj.add(new ArrayList<>());
        System.out.println(removeEdge(adj, 0, 2) + " " + adj);
        System.out.println(removeEdge(adj, 0, 2)); // already gone
    }
}

Output

true [[1], [3], [3], []]
false

List.of(...) creates an immutable list that throws UnsupportedOperationException on remove, so the mutable example copies the lists into ArrayLists. A call like list.remove(v) with an int argument removes the element at index v, not the value v. Use indexOf first, or list.remove(Integer.valueOf(v)) to remove by value.

Time: O(deg(u)): finding v scans u's list, and remove shifts the elements after it. Space: O(1).

Choosing the removal method

Method	Time	Order of the other neighbors	Removes
`list.remove(i)`	`O(deg u)`	kept	one edge
`list.set(i, list.get(last))` then `list.remove(last)`	`O(1)` after finding `i`	changed: the last neighbor moves into slot `i`	one edge
`list.removeIf(w -> w == v)`	`O(deg u)`	kept	every copy of the edge

Neighbor order matters only if something depends on it, such as the exact BFS or DFS visiting order. Otherwise, swapping with the last element is the fastest, because removing the last element of an ArrayList shifts nothing.

Undirected graphs and frequent changes

In an undirected graph, the edge is stored in both adj.get(u) and adj.get(v), so remove it from both lists.
If edges are added and removed often, store each vertex's neighbors in a HashSet<Integer> instead of a list. Removing an edge is then O(1) expected, at the cost of an unspecified neighbor order.

Java

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Main {
    public static void main(String[] args) {
        List<Set<Integer>> adj = new ArrayList<>();
        adj.add(new HashSet<>(Set.of(1, 2)));
        adj.add(new HashSet<>(Set.of(0)));
        adj.add(new HashSet<>(Set.of(0)));
        // Remove the undirected edge 0 - 2 from both ends:
        boolean removed = adj.get(0).remove(2) & adj.get(2).remove(0);
        System.out.println(removed + " " + adj.get(0).contains(2) + " " + adj.get(2).isEmpty());
    }
}

Output

true false true

Brute force: rebuild the graph without the edge

Optimal: edit only adj.get(u)

Choosing the removal method

Undirected graphs and frequent changes

Optimal: edit only `adj.get(u)`