What is a graph in data structures?

A graph is a non-linear data structure consisting of a finite set of vertices (or nodes) and a finite set of edges (or links) that connect these vertices. It's a powerful and versatile structure used to model relationships between objects.

Core Components

A graph G can be formally defined as G = (V, E), where V is a set of vertices and E is a set of edges. Each edge (u, v) in E connects two vertices u and v in V.

Vertices (Nodes)

Vertices are the fundamental entities or points in a graph. They can represent anything from people in a social network to cities on a map, or states in a finite automaton.

Edges (Links)

Edges are connections between two vertices. They represent the relationship or interaction between the entities. Edges can be directed or undirected, and can also have associated weights.

Types of Graphs

• Undirected Graph: Edges have no direction (e.g., A is connected to B implies B is connected to A).
• Directed Graph (Digraph): Edges have a specific direction (e.g., A leads to B does not imply B leads to A).
• Weighted Graph: Edges have a numerical value (weight) associated with them, representing cost, distance, time, etc.
• Unweighted Graph: Edges have no associated value; all connections are considered equal.
• Cyclic Graph: Contains at least one cycle (a path that starts and ends at the same vertex).
• Acyclic Graph: Contains no cycles.
• Connected Graph: There is a path between every pair of vertices.
• Disconnected Graph: Not all vertices are reachable from each other.

Common Graph Representations

1. Adjacency Matrix

An adjacency matrix is a square matrix (V x V) where V is the number of vertices. If there's an edge from vertex i to vertex j, the cell M[i][j] is 1; otherwise, it's 0. For weighted graphs, M[i][j] stores the weight of the edge.

graph = [
  [0, 1, 0, 1],
  [1, 0, 1, 0],
  [0, 1, 0, 1],
  [1, 0, 1, 0]
] # For an undirected graph with 4 vertices

2. Adjacency List

An adjacency list represents a graph as an array of lists. The index of the array represents a vertex, and each element in its list contains the vertices adjacent to the current vertex. This is generally more memory-efficient for sparse graphs.

graph = {
  0: [1, 3],
  1: [0, 2],
  2: [1, 3],
  3: [0, 2]
} # For an undirected graph with 4 vertices

Applications of Graphs

• Social Networks: Representing users as vertices and friendships/connections as edges.
• GPS and Mapping: Cities as vertices, roads as edges, and distances as weights.
• Network Topology: Computers as vertices, network connections as edges.
• Web Page Ranking: Web pages as vertices, hyperlinks as directed edges.
• Recommendation Systems: Users and items as vertices, ratings/interactions as edges.