Solution: Remove Edge from a Directed Graph

Statement

Given an adjacency list of a directed graph consisting of n vertices, modify the list after removing an edge between the source and destination vertices.

Constraints:

• $0 \leq$ n $\leq 10^2$

• $0 \leq$edges.length $\leq n(n-1)/2$

• edges[i].length $== 2$

• $1 \leq$source, destination $\leq$n

• source$\neq$destination

• There are no multiple edges between any two vertices

• There are no self-loops

Solution

This solution aims to demonstrate the removal of an edge between two vertices in a graph represented by an adjacency list. An adjacency list is a common way to represent a graph in which each vertex is associated with a list of its neighboring vertices. By removing an edge between two vertices, we effectively sever their connection, altering the graph’s structure accordingly.

Removing an edge from a directed graph’s adjacency list involves traversing the dictionary structure to locate and manipulate the vertices involved. First, we ensure that both the source and destination vertices are present in the adjacency list. This is important because attempting to remove a nonexistent edge may lead to errors or unexpected behavior. If both the vertices exist, then we remove the edge connecting them. Given the directed nature of the graph, we only need to remove the destination vertex from the adjacency list of the source vertex. This step ensures that the graph structure remains consistent and accurately reflects the absence of the specified edge.

Now, let’s look at the algorithm for this approach:

1. Check if the source vertex, source exists in the graph’s adjacency list, and if the destination vertex, destination exists in the adjacency list of the source vertex.

2. If both vertices exist, remove the destination vertex from the adjacency list of the source vertex only since the graph is directed.

3. Return the modified graph.

Let’s look at the illustration below to better understand the solution: