Generated with Monsha

Save this resource to edit, expand, or export it, or create more resources for free.

Introduction to Graph Data Structures

Handout
Grade 10
English (UK)

Introduction to Graph Data Structures

What are Graph Data Structures?

A graph is a non-linear data structure that consists of a finite set of nodes (also called vertices) and a set of edges (or arcs) that connect these nodes. Think of it like a network where each point is a node and the lines connecting them are edges. Graphs are incredibly versatile and are used to model various real-world scenarios, from social networks to transportation systems.

Key Components

  • Vertices (Nodes): These are the fundamental entities in a graph. Each vertex represents an object or a point in the network. For example, in a social network, each person would be a vertex.
  • Edges: These are the connections between vertices. An edge indicates a relationship or a path between two nodes. Edges can have properties, such as a 'weight' or 'direction'.

Types of Graphs

  1. Undirected Graph: In an undirected graph, edges have no direction. If an edge connects vertex A and vertex B, it means you can travel from A to B and from B to A. Think of a two-way street.
  1. Directed Graph (Digraph): In a directed graph, edges have a specific direction. An edge from A to B means you can only travel from A to B, not necessarily from B to A. This is like a one-way street.
  1. Weighted Graph: Both directed and undirected graphs can be weighted. A weighted graph has a numerical value (a 'weight' or 'cost') associated with each edge. This weight could represent distance, time, cost, or capacity. For instance, in a road network, the weight might be the distance between two cities.

Applications

Graphs are used in many areas, including:
  • Social Networks: Representing friendships or connections between people.
  • Navigation Systems: Finding the shortest route between two locations (e.g., Google Maps).
  • Computer Networks: Modelling how computers and devices are connected.
  • Airline Routes: Showing flight paths between cities.
Understanding graph data structures is crucial for solving complex problems involving relationships and networks.
graph LR A[Start] -->|Cost 10| B(Node B) B -->|Cost 5| C{Node C} C -->|Cost 8| D[End] A -->|Cost 7| C D -->|Cost 3| B