Thread Academy

Graph Networks

Model networks and relationships with nodes and edges.

  • Define and explain Graph Networks in your own words
  • Use key terms such as node accurately
  • Apply what you have learned to new examples and questions
  • Avoid the common mistakes learners make with this topic

This lesson focuses on Graph Networks: model networks and relationships with nodes and edges.

Definition: Graph Networks

Model networks and relationships with nodes and edges.

Key ideas

Graphs model the real world

Roads, friendships, computer networks and dependencies are all graphs: nodes for places or things, edges for connections. Weighted edges let algorithms such as Dijkstra's find the cheapest route. Unlike trees, graphs can contain cycles — paths that loop back — which algorithms must handle to avoid going round forever.

Trees turn searching into halving

A binary search tree keeps smaller values left and larger values right, so each comparison discards half the tree — the same idea as binary search, built into the structure. Traversals visit nodes in different orders: in-order on a binary search tree yields the values sorted. Insert order shapes the tree, and a badly ordered insert degrades it into a slow linked list.

Key term — node: A single element in a tree or graph, holding data plus links to other nodes.

Worked example: Graph Networks

In a road network modelled as a graph, what do nodes, edges and weights represent?

Nodes are junctions (or towns), edges are the roads between them, and weights are distances or travel times.

Answer: Nodes are junctions (or towns), edges are the roads between them, and weights are distances or travel times.

Common mistakes
  • Forgetting graphs can contain cycles Correction: when traversing a graph, keep a visited set — otherwise your algorithm can loop around a cycle forever.
  • Popping or dequeuing from an empty structure Correction: always check the structure is not empty first — removing from nothing causes an underflow error.

Practice

Which structure models a web browser's back button: stack or queue? Why?
The last page visited is the first you go back to.

A stack — each new page is pushed, and Back pops the most recent page, which is last-in, first-out.

A queue holds [A, B, C] with A at the front. After one dequeue and one enqueue of D, what is the queue?
Dequeue removes from the front; enqueue adds at the rear.

[B, C, D] — A leaves from the front and D joins at the rear.

Insert 5, 3, 8, 1 into an empty binary search tree in that order. What is the root's left child?
Smaller values go left of each node.

3 — it goes left of root 5, and then 1 goes left of 3.

What does an in-order traversal of a binary search tree produce?
Left subtree, node, right subtree — with smaller values on the left.

The values in ascending sorted order.

Quick check

Graph Networks — quick check

Which of these best defines "node"?

A single element in a tree or graph, holding data plus links to other nodes.

True or false: a stack can be used to check whether brackets in an expression are balanced.

True — push each opening bracket and pop on each closing one; the last opened must be the first closed, which is exactly LIFO.
Key takeaways
  • Graph Networks: model networks and relationships with nodes and edges.
  • Graphs model the real world: Roads, friendships, computer networks and dependencies are all graphs: nodes for places or things, edges for connections.
  • edge: A connection between two nodes in a graph, which may have a direction and a weight such as a distance.
  • Watch out for: forgetting graphs can contain cycles
← Tree StructuresBack to Grade 11 chaptersRelated resources →