Graphs
Computer Science: OCR A Level, topic 4.2.4
Directed & Undirected Graphs
Graphs are data structures used to represent data items which have connections between them, such as locations on a map or products on an e-commerce website.
Graphs
- Graphs consist of ‘nodes’ or ‘vertices’ which are joined by ‘arcs’ or ‘edges’ and can either be directed or undirected.
- A directed graph is one where the connections between the nodes only go in one direction (the arcs are represented as arrows).
- In an undirected graph, the connections are two-way.
Graph traversal
- There are two methods of traversing a graph:
- Depth-first.
- Breadth-first.
Depth-first traversal
- Depth-first traversal involves travelling down one route as far as possible, before reversing and travelling as far down the next route as possible.
- In the graph shown, depth-first traversal would involve visiting the nodes in the following order:
- A, B, E, C, D, G, F
Breadth-first
- Breadth-first traversal involves visiting all the adjoining nodes for each node in turn.
- In the graph shown, breadth-first traversal would involve visiting the nodes in the following order:
- A, B, C, E, D, F, G
Test yourself on Graphs
In which order would a breadth-first traversal visiting the nodes in the graph shown?
In which order would a depth-first traversal visiting the nodes in the graph shown?