Suggest an edit

Improve this article

Refine the answer for “What does a graph consist of?”. Your changes go to moderation before they’re published.

Approval required

Content

What you’re changing

Title (EN)

Short answer (EN)

Shown above the full answer for quick recall.

Answer (EN)

## 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)

1. A graph is a pair of sets (V, E): vertices and edges.
2. Edges can be directed/undirected and can have a weight; loops and parallel edges are possible.
3. Key concepts: degree, path, cycle, connected components.
4. 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).

Markdown · drag & drop images · ⌘B / ⌘I shortcuts821 words

For the reviewer

Note to the moderator (optional)

Visible only to the moderator. Helps review go faster.