Generated with Monsha

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