4.2.4

Graphs

Test yourself

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.

Illustrative background for GraphsIllustrative background for Graphs ?? "content

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.
Illustrative background for Graph traversalIllustrative background for Graph traversal ?? "content

Graph traversal

  • There are two methods of traversing a graph:
    • Depth-first.
    • Breadth-first.
Illustrative background for Depth-first traversalIllustrative background for Depth-first traversal ?? "content

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
Illustrative background for Breadth-firstIllustrative background for Breadth-first ?? "content

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

Jump to other topics

1Components of a Computer

2Software & Software Development

3Exchanging Data

4Data Types, Data Structures & Algorithms

5Legal, Moral, Cultural & Ethical Issues

6Elements of Computational Thinking

6.1Thinking Abstractly

6.2Thinking Ahead

6.3Thinking Procedurally

6.4Thinking Logically

6.5Thinking Concurrently

7Problem Solving & Programming

8Algorithms

Unlock your full potential with Seneca Premium

  • Unlimited access to 10,000+ open-ended exam questions

  • Mini-mock exams based on your study history

  • Unlock 800+ premium courses & e-books

Get started with Seneca Premium