Graphs

Overview

Recall questions on directed, undirected and weighted graphs, adjacency matrices and adjacency lists and when to use each, creating graphs and adding or removing nodes and edges, traversals, visited lists, and how a tree relates to a graph.

What you need to know

Answer each one before you reveal it.

Questions from this subtopic

Each one with the model answer underneath.

1. 1

   What is a graph in computing?

   Model answer

   A data structure consisting of a set of nodes (also called vertices) joined by edges (also called arcs). Unlike a tree, a graph places no restriction on the connections: a node may be joined to any number of others, cycles are allowed, and the graph may even be in disconnected pieces.

2. 2

   What is the difference between a directed and an undirected graph?

   Model answer

   In an undirected graph an edge simply joins two nodes and can be travelled in either direction, so if A is joined to B then B is joined to A. In a directed graph (or digraph) each edge has a direction, drawn as an arrow, and can only be travelled that way, so an edge from A to B does not imply one from B to A. A one-way street system is directed; a friendship network where friendship is mutual is undirected.

3. 3

   What is a weighted graph?

   Model answer

   A graph in which each edge carries a value, its weight, representing a cost of using that connection - typically a distance, time, price or capacity. The weight is written next to the edge on a diagram. Weighted graphs are what shortest-path problems operate on, and a graph may be both weighted and directed, for example a road network with one-way streets and journey times.

4. 4

   Give three real-world things that are naturally modelled as graphs.

   Model answer

   A road or rail network, with junctions as nodes and roads as weighted edges. A social network, with people as nodes and relationships as edges, directed if following is one-way. A computer network, with devices as nodes and links as edges. Others include the web (pages linked by hyperlinks, a directed graph), state transition diagrams and dependency between tasks in a project.

5. 5

   Describe how an adjacency matrix stores a graph.

   Model answer

   It is a two-dimensional array with one row and one column for every node. The cell at row i, column j holds 1 (or the edge's weight) if there is an edge from node i to node j, and 0 or a null value if there is not. For an undirected graph the matrix is symmetrical about the leading diagonal, because every edge is recorded twice; for a directed graph it generally is not.

6. 6

   A graph has nodes A, B, C, D and undirected edges A-B, A-C, B-D and C-D. Write out its adjacency matrix.

   Model answer

   With rows and columns in the order A, B, C, D: row A is 0 1 1 0; row B is 1 0 0 1; row C is 1 0 0 1; row D is 0 1 1 0. Every edge appears twice, once in each direction, so the matrix is symmetrical about the diagonal from top left to bottom right, and the diagonal itself is all zeros because no node has an edge to itself.

Other ways to work this

The same content, four other ways.

What is inside Levo

Six ways to work the same material.