What does a graph consist of?

AlgorithmsJunior~3 min read

Short answer

A graph is an abstract structure consisting of:

a set of vertices V (nodes);
a set of edges E, where each edge connects one or two vertices.

Edges can be directed or undirected, weighted or unweighted; loops and parallel edges (in multigraphs) are allowed.

Detailed answer

Basic elements of a graph

Vertices (V, nodes): objects/entities. They can have an identifier, a label, and attributes (for example, a name, coordinates, properties).
Edges (E): connections between vertices. In an undirected graph an edge is an unordered pair {u, v}, in a directed graph it is an ordered pair (u → v). Edges can hold weights/costs and other attributes.

Edge properties and graph variants

Directionality: directed (arcs) vs undirected. In a directed graph you distinguish out-degree from in-degree.
Weighting: an edge can have a weight (cost, distance, bandwidth). In an unweighted graph all weights are equal, usually 1.
Multiplicity: a simple graph (no loops or parallel edges) vs a multigraph (parallel edges allowed).
Loops: an edge connecting a vertex to itself (u → u).
Labels/attributes: on both vertices and edges (for example, a connection type, timestamps).

Basic concepts

Adjacency and incidence: vertices u and v are adjacent if there is an edge between them; an edge is incident to its vertices.
Vertex degree: the number of incident edges. For a directed graph: in-degree and out-degree.
Path/walk and path length: a sequence of vertices connected by edges; length is the number of edges or the sum of weights.
Cycle and acyclicity: a cycle starts and ends at the same vertex; the absence of cycles is called an acyclic graph (for example, a DAG).
Connected components: maximal subsets of vertices between which paths exist.
Special kinds: a tree (connected and acyclic), a forest (a set of trees), a complete graph, a bipartite graph.

How to store a graph in memory

Adjacency List: memory-efficient for sparse graphs; fast neighbor traversal.

// JS: directed weighted graph (adjacency list) const graph = { A: [{ to: 'B', w: 5 }, { to: 'D', w: 1 }], B: [{ to: 'C', w: 2 }], C: [], D: [{ to: 'C', w: 3 }] }; // traverse A's neighbors for (const edge of graph.A) { console.log(`A -> ${edge.to} (w=${edge.w})`); }
Adjacency Matrix: O(1) edge-existence check, convenient for dense graphs; requires O(n²) memory.

// Adjacency matrix for vertices [A,B,C,D] // 0 means no edge, otherwise the weight const V = ['A','B','C','D']; const M = [ /*A*/ [0, 5, 0, 1], /*B*/ [0, 0, 2, 0], /*C*/ [0, 0, 0, 0], /*D*/ [0, 0, 3, 0] ]; // Check edge A->B const i = V.indexOf('A'); const j = V.indexOf('B'); console.log(M[i][j] !== 0); // true
Edge List: simple storage for a set of edges; convenient for algorithms that need a full list of edges (for example, Kruskal's).

// Edge list (u, v, w) const edges = [ ['A','B',5], ['A','D',1], ['B','C',2], ['D','C',3] ];

Mini example: a directed weighted graph

Let V = {A, B, C, D}, E = {(A→B, 5), (A→D, 1), (B→C, 2), (D→C, 3)}.

Out-degree: deg⁺(A)=2, deg⁺(B)=1, deg⁺(C)=0, deg⁺(D)=1.
In-degree: deg⁻(A)=0, deg⁻(B)=1, deg⁻(C)=2, deg⁻(D)=1.
Shortest path by weight A → C: A→D→C (weight 1+3=4) is shorter than A→B→C (5+2=7).

// Simple Dijkstra for positive weights (JS)
function dijkstra(adj, src) {
  const dist = Object.fromEntries(Object.keys(adj).map(v => [v, Infinity]));
  dist[src] = 0;
  const visited = new Set();

  while (visited.size < Object.keys(adj).length) {
    let u = null, best = Infinity;
    for (const v of Object.keys(adj)) {
      if (!visited.has(v) && dist[v] < best) { best = dist[v]; u = v; }
    }
    if (u === null) break;
    visited.add(u);
    for (const { to, w } of adj[u]) {
      if (dist[u] + w < dist[to]) dist[to] = dist[u] + w;
    }
  }
  return dist;
}

const adj = {
  A: [{ to: 'B', w: 5 }, { to: 'D', w: 1 }],
  B: [{ to: 'C', w: 2 }],
  C: [],
  D: [{ to: 'C', w: 3 }]
};

console.log(dijkstra(adj, 'A')); // { A:0, B:5, C:4, D:1 }

How to answer briefly in an interview (30-60 seconds)

A graph is a pair of sets (V, E): vertices and edges.
Edges can be directed/undirected and can have a weight; loops and parallel edges are possible.
Key concepts: degree, path, cycle, connected components.
Storage: adjacency list, adjacency matrix, edge list (depending on density and the task).

Frequent mistakes

Substituting the definition of a graph with its implementation (for example, "it's an object with arrays of neighbors").
Forgetting to mention directionality/weights/loops and multigraphs.
Confusing a vertex's degree with its number of neighbors in directed graphs (in and out must be distinguished).
Choosing an inefficient representation (for example, a matrix for a very sparse graph).

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.