Graph

Nodes and the connections between them — no strict hierarchy.

What it is

A graph is a set of nodes (vertices) connected by edges, with no root and no rule about how many connections a node can have — unlike a tree, it can have cycles. The adjacency list (a map of node → its neighbors) is the go-to representation because it's compact and fast to traverse; an adjacency matrix trades memory for O(1) 'are these two connected?' checks.

Real-world examples

A social network — people are nodes, friendships are edges, and there's no single 'root' person.
A road map — intersections are nodes, roads are edges, and you can loop back to where you started.

Where you've probably used this already

Modeling any many-to-many relationship: friend networks, dependency graphs (package.json's dependency tree is actually a graph, since packages can share sub-dependencies), service call graphs in microservices.
Detecting circular dependencies in a build system or import graph.
Recommendation systems ('people who liked X also liked Y') are graph traversal/scoring under the hood.

Complexity

Add vertex/edge O(1) with adjacency list

Traverse (BFS/DFS) O(V + E) — vertices plus edges

Check if edge exists O(degree of vertex) with a list, O(1) with a matrix

Code

class Graph {
  constructor() {
    // Stores the adjacency list: Node -> Array of Neighbors
    this.adjacencyList = new Map();
  }

  // Add a new vertex to the graph
  addVertex(vertex) {
    if (!this.adjacencyList.has(vertex)) {
      this.adjacencyList.set(vertex, []);
    }
  }

  // Add an undirected edge between vertex1 and vertex2
  addEdge(vertex1, vertex2) {
    // Ensure both vertices exist in our graph first
    if (!this.adjacencyList.has(vertex1)) this.addVertex(vertex1);
    if (!this.adjacencyList.has(vertex2)) this.addVertex(vertex2);

    // Push connections to each other's lists (undirected)
    this.adjacencyList.get(vertex1).push(vertex2);
    this.adjacencyList.get(vertex2).push(vertex1);
  }

  // Print the graph representation to the console
  printGraph() {
    for (let [vertex, neighbors] of this.adjacencyList) {
      console.log(`${vertex} -> ${neighbors.join(', ')}`);
    }
  }
}

// --- Usage Example ---
const socialNetwork = new Graph();

// Adding individual users (vertices)
socialNetwork.addVertex("Marky");
socialNetwork.addVertex("Alwyn");
socialNetwork.addVertex("Arnijune");

// Establishing connections (edges)
socialNetwork.addEdge("Marky", "Alwyn");
socialNetwork.addEdge("Alwyn", "Arnijune");
socialNetwork.addEdge("Arnijune", "Marky");

// View the final graph structure
socialNetwork.printGraph();
// Output:
// Alice -> Bob, Charlie
// Bob -> Alice, Charlie
// Charlie -> Alice, Bob