Graphs: Traversing, Adding & Removing Data (OCR A Level Computer Science)
Revision Note
Author
James WoodhouseExpertise
Computer Science
Graphs: Traversing, Adding & Removing Data
How do you Traverse a Graph?
There are two approaches to traversing a graph:
A breadth-first search
A depth breadth-first search
Breadth-First Search
A breadth-first search is a graph traversal algorithm which systematically visits all neighbours of a given vertex before moving on to their neighbours. It then repeats this layer by layer.
This method makes use of a queue data structure to enqueue each node as long as it is not already in a list of visited nodes.
Take the example above, the root node, Dunkirk, would be set as the current node and then added to the visited list
Dunkirk |
|---|
Moving from left to right, we must check if the connected node isn't already in the visited list, if it is not, it is enqueued to the queue.
The first version of the queue would have appeared as
Front Pointer | Back Pointer | Position | Data |
|---|---|---|---|
|
| 5 |
|
|
| 4 |
|
|
| 3 |
|
→ | → | 2 | Hartlepool |
→ | → | 1 | Moulton |
→ | → | 0 | Bolton |
→ | → | -1 | Empty |
That linked vertex is then added to the visited list. Finally, it is removed from the queue as this process repeats. This means that all nodes, from left to right are enqueued to the queue in turn, before being added to the visited list, and then dequeued from the queue
Output all of the visited vertices
Our final visited list would appear as
Dunkirk, Bolton, Moulton, Hartlepool, Frogmore, Teesside, Cardiff |
|---|
The final version of the queue would have appeared as
Front Pointer | Back Pointer | Position | Data |
|---|---|---|---|
→ | → | 5 | Cardiff |
→ | → | 4 | Teesside |
→ | → | 3 | Frogmore |
→ | → | 2 | Hartlepool |
→ | → | 1 | Moulton |
→ | → | 0 | Bolton |
→ | → | -1 | Empty |
Depth-First Search
A depth-first search is a graph traversal algorithm which uses an edge-based system.
This method makes use of a stack data structure to push each visited node onto the stack and then pop them from the stack when there are no nodes left to visit.
Exam Tip
There is no right method to use when performing a depth-first search, it simply depends on how the algorithm is implemented. Most mark schemes commonly traverse the left-most path first, therefore that will be used in this example.
Using the example from above, Dunkirk, would be set as the current node and then added to the visited list
Dunkirk |
|---|
Then check if the connected node isn't already in the visited list, if it is not, it pushed to the stack.
The first version of the stack would appear as
Pointer | Position | Data |
|---|---|---|
| 5 |
|
| 4 |
|
| 3 |
|
→ | 2 | Bolton |
→ | 1 | Moulton |
→ | 0 | Hartlepool |
→ | -1 | Empty |
Next, any connected node that is not on the visited list is then pushed to the stack.
Then pop the stack to remove the item and set it as the current node.
Output all of the visited nodes
Our final visited list would appear as
Dunkirk, Bolton, Frogmore, Moulton, Hartlepool, Teesside, Cardiff |
|---|
You could visualise how the graph has been traversed below, with the left-most column first, then the middle, then the right-most column.
Adding & Removing Data in Graphs
There is no single algorithm for adding or deleting a node in a graph. This is because a graph can have a number of nodes connected to any number of other nodes.
As a result, it is more important that there are a clear set of instructions to easily traverse the graph to find the specific node.
A Binary Tree is a special type of graph and it does have an algorithm for adding and deleting items. This is covered in the content titles’ Binary Search Trees’.
Exam Tip
It is important to note that it is not important what the graph looks like, but which vertices are connected.
Worked Example
A puzzle has multiple ways of reaching the end solution. The graph below shows a graph that represents all possible routes to the solution. The starting point of the game is represented by A, the solution is represented by J. The other points in the graph are possible intermediary stages.
The graph is a visualisation of the problem.
i. Identify one difference between a graph and a tree [1]
A graph has cycles [1]
A graph can be directed/undirected [1]
A tree has a hierarchy (e.g. Parent/Child) [1]
ii. Explain how the graph is an abstraction of the problem [2]
The puzzle is not shown in the diagram [1]
The graph shows different sequences of sub-problems in the puzzle that can be solved to get the final solution [1]
The puzzle does not have all states visible at once [1]
iii. Identify two advantages of using a visualisation such as the one shown above [2]
Visualisation benefits humans rather than computers [1]
Visualisations present the information in a simpler form to understand [1]
Visualisation can best explain complex situations [1]
You've read 0 of your 0 free revision notes
Get unlimited access
to absolutely everything:
- Downloadable PDFs
- Unlimited Revision Notes
- Topic Questions
- Past Papers
- Model Answers
- Videos (Maths and Science)
Did this page help you?