Graph Basics

Graphs are a general way to model relationships between entities:

  • Nodes (vertices) represent entities.
  • Edges represent relationships or connections between them.

Graphs are ubiquitous in:

  • Social networks.
  • Recommendation systems.
  • Road maps and routing.
  • Dependency graphs in build systems or package managers.

Terminology

  • Vertex (node) – a point in the graph.
  • Edge – a connection between two vertices.
  • Degree of a vertex – number of edges incident to it.
  • Path – a sequence of vertices where each consecutive pair is connected by an edge.
  • cycle – a path that starts and ends at the same vertex with at least one edge.
  • Connected component – a maximal set of vertices where every pair is connected by some path.

Graphs come in different flavors:

  • Directed vs undirected – edges have direction or not.
  • Weighted vs unweighted – edges may carry a cost, distance, or weight.

These variants are covered conceptually in later articles in this section.

Graph Representation

Common ways to represent graphs in code:

  • Adjacency list:
    • For each node, store a list of its neighbors.
    • Efficient for sparse graphs; memory O(n + m) where n is vertices, m edges.
  • Adjacency matrix:
    • n x n matrix, matrix[u][v] indicates presence (and possibly weight) of an edge.
    • Simple but uses O(n²) memory.

Adjacency lists are the default in most algorithm implementations.

Graph Traversals

Two fundamental traversals:

  • Depth‑First Search (DFS):
    • Explore as deep as possible before backtracking.
    • Implemented recursively or with an explicit stack.
  • Breadth‑First Search (BFS):
    • Explore level by level using a queue.
    • Finds shortest path (fewest edges) in unweighted graphs.

Many graph algorithms build on these primitives.

Why Graphs Matter

Graphs are the right abstraction anytime:

  • Relationships are not strictly hierarchical (unlike trees).
  • Entities can have many arbitrary connections.

Examples:

  • Users following each other.
  • Servers and network links.
  • Courses and prerequisite relationships.

Later articles in this series dive into:

  • Different graph types (directed/undirected, weighted/unweighted).
  • Representations and trade‑offs.
  • How data structures like adjacency lists and matrices support graph algorithms.