Community resourceWorksheet

OCR H446 1.4.2 Graph creation and operations

Part 8 of 14 · H446 1.4.2 · Data structures

Reading a graph is one skill; changing one without leaving dangling references is another, and H446 1.4.2 examines both. Here a venue network gains and loses locations and routes, so students maintain an adjacency list through additions, removals and traversal of a graph that contains cycles.

Students will:

  • create vertices and edges in an adjacency-list graph
  • add directed and undirected edges without creating duplicates
  • remove a vertex together with every edge that points at it
  • apply a sequence of changes and give the full adjacency list after each one
  • explain why traversal of a cyclic graph needs a visited set, and what reachable means

Inside: 7 explanation cells, 1 multiple-choice question, 1 fill-in-the-blanks cell, 2 written answers and 3 Python tasks. 22 marks, about 45 to 55 minutes.

Series: H446 1.4.2 · Data structures, part 8 of 14.

Shared by Coding PathwayVerified teacher

  • 14 cells
  • About 45 minutes
  • CC BY-SA 4.0
  • Shared 31 Aug 2026
  • Updated 1 Oct 2026

Preview

The whole resource, exactly as a class sees it. Answers and marking are held back.

Graph creation and operations

A graph changes when a location or route opens or closes. Every update must preserve the meaning of the representation. For example, deleting one node also requires the removal of edges that still point to it.

By the end, you will be able to

  • create vertices and edges;
  • add and remove directed and undirected edges;
  • remove a vertex and its incident edges;
  • traverse reachable nodes without processing a cycle forever.

Worked invariant

Directed add A→B changes A’s neighbour list only. Undirected add A↔B changes both A and B lists. Removing vertex B must remove its own entry and every incoming reference to B.

Traversal keeps a visited set. Without it, a cycle A→B→A can repeat forever.

Worked example
graph = {"A": ["B", "C"], "B": ["C"], "C": ["A"], "D": []}
visited = set()
frontier = ["A"]
while frontier:
    node = frontier.pop()
    if node not in visited:
        visited.add(node)
        for neighbour in graph[node]:
            frontier.append(neighbour)
print(sorted(visited))
Multiple choice1 mark

When removing vertex B from an adjacency-list graph, what else must be removed?

  • AAll weights everywhere
  • BReferences to B in other neighbour lists
  • CEvery isolated vertex
  • DThe visited set permanently

Guided state updates

Start A:[B], B:[C], C:[]. Add directed C→A; remove edge A→B; remove vertex B. Write the full dictionary after each change and check every referenced vertex exists.

Written answer4 marks

Apply those three operations and give the final adjacency list.

Preserve direction and remove every reference to a deleted vertex.

Students type their answer here.

Independent transfer: safe directed graph functions

Implement add_edge(graph,start,end) so missing vertices are created and duplicate edges are not added.

Coding task5 marks
def add_edge(graph, start, end):
    if start not in graph:
        graph[start] = []
    if end not in graph:
        graph[end] = []

    # Keep this directed edge unique.
    if ...:
        ...
    return graph

Independent mutation: remove a vertex

Implement remove_vertex(graph, target). Remove target's own adjacency-list entry and every edge that points to target. Leave other vertices and edges unchanged.

Coding task5 marks
def remove_vertex(graph, target):
    if target in graph:
        ...

    for node in graph:
        # Rebuild each neighbour list without target.
        graph[node] = [...]
    return graph
Written answer3 marks

Explain why visited is necessary when traversing a cyclic graph and what reachable means.

Use the A→B→A example.

Students type their answer here.

Closed-book checkpoint

Complete each sentence from memory. There is no answer bank and correctness is held for teacher review.

Fill in the blanks4 marks
Adding an undirected edge records completion 1 neighbour links; a directed edge records only the stated completion 2. Removing a vertex must also remove every completion 3 edge reference. A traversal keeps a completion 4 set to prevent repeated visits in a cycle.

Review your work

Check that adding or removing an edge leaves every adjacency reference valid.