Graph Insertion, Deletion and Representation

A graph contains vertices and edges. An undirected edge connects a pair without a direction; a directed edge has an ordered source and destination. A weighted graph associates an edge with a value such as distance or cost. Specify whether parallel edges and self-loops are allowed before choosing a representation.

In this lesson’s simple undirected graph, an adjacency dictionary maps each vertex to a set of neighbours. An edge A—B appears in both A’s set and B’s set. A set prevents duplicate copies of the same connection, and the function rejects self-loops. A directed representation would not automatically add the reverse edge, and a weighted version would need to store weights as well as membership.

To add an undirected edge, ensure both vertices exist and add each endpoint to the other’s neighbour set. Removing an edge should remove both memberships. Deleting vertex B must also remove B from every surviving neighbour collection. Deleting only graph[B] leaves dangling references that a traversal could later follow.

The example uses discard so that removing an absent neighbour is harmless under this operation contract. It iterates the neighbour sets while changing those sets, rather than adding or removing dictionary keys during that iteration. Only after incident references have been removed does it delete the vertex’s own dictionary entry. State how a missing vertex is handled: here removal simply has no effect.

An adjacency matrix uses a row and column per vertex, so a direct edge-presence lookup can be constant time when indices are known. Its space is proportional to V² even when few edges exist. Adding or deleting vertices may require resizing or maintaining a separate active-index policy.

An adjacency-list representation stores the vertices and actual connections, giving space proportional to V+E under the usual model. Finding or removing a neighbour depends on whether neighbours use lists, sets or another structure. For a directed graph, deleting a vertex must remove incoming as well as outgoing references. Recommend a representation from graph density and operation needs, and preserve its invariants when updating it.

def add_edge(graph, first, second):
    if first == second:
        raise ValueError("self-loops are not allowed in this model")
    graph.setdefault(first, set()).add(second)
    graph.setdefault(second, set()).add(first)

def remove_vertex(graph, vertex):
    for neighbours in graph.values():
        neighbours.discard(vertex)
    graph.pop(vertex, None)

graph = {}
add_edge(graph, "A", "B")
add_edge(graph, "B", "C")
add_edge(graph, "A", "C")
remove_vertex(graph, "B")
print({key: sorted(graph[key]) for key in sorted(graph)})

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.