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 3 Sept 2026

Preview

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

Graph creation and operations

A venue network changes as locations and routes open or close. Operations must preserve direction and remove invalid references.

By the end, you will be able to

  • create vertices and edges;
  • add and remove directed/undirected edges;
  • remove a vertex and incident edges;
  • traverse reachable nodes without revisiting forever.

Reactivate: an adjacency list maps a node to neighbours.

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?

  • AReferences to B in other neighbour lists
  • BAll weights everywhere
  • 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):
    pass

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):
    pass
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 responses

Check every response against its command word and the supplied constraints. Strengthen unsupported answers with accurate method, mechanism, state or contextual consequence before submitting.