Graph Data Structure Terminology

Learn Graph Data Structure Terminology with practical examples, explanations, best practices, and real-world coding techniques.

Understanding Graph Terminology

A graph is a non-linear data structure used to represent relationships between objects. The objects are called vertices or nodes, while the relationships between them are represented by edges.

Graph terminology is important because graph algorithms such as Breadth-First Search (BFS), Depth-First Search (DFS), Dijkstra's algorithm, and topological sorting depend on these concepts. Understanding the terminology first makes graph problems much easier to read and solve.

1. Vertex or Node

A vertex is an individual object represented in a graph. It is also commonly called a node.

For example, in a social network, each person can be represented as a vertex. In a computer network, each server or device can be represented as a vertex. 

const vertices = ['A', 'B', 'C', 'D'];

2. Edge

An edge represents a relationship or connection between two vertices. If vertices A and B are connected, the edge can be represented as: 

A --- B

In an undirected graph, the connection between A and B can be traveled in either direction. In a directed graph, the edge has a specific direction.

3. Directed Edge

A directed edge has a source and a destination. It is represented using an arrow. 

A ---> B

This means that the edge goes from A to B. It does not necessarily mean that B can travel back to A.

4. Undirected Edge

An undirected edge represents a two-way relationship between vertices. 

A --- B

If A is connected to B, B is also connected to A.

5. Adjacent Vertices

Two vertices are called adjacent when there is a direct edge connecting them. 

A --- B --- C

Here, A and B are adjacent, and B and C are adjacent. A and C are not adjacent because there is no direct edge between them.

6. Neighbor

A neighbor of a vertex is another vertex directly connected to it. The terms adjacent vertex and neighbor are often used interchangeably. 

A --- B
|
C

The neighbors of A are B and C.

7. Degree of a Vertex

The degree of a vertex in an undirected graph is the number of edges connected to that vertex. 

    B
    |
C---A---D
    |
    E

Vertex A has four directly connected edges, so its degree is 4.

8. In-Degree and Out-Degree

In a directed graph, degree is separated into in-degree and out-degree.

  • In-degree: Number of edges entering a vertex.
  • Out-degree: Number of edges leaving a vertex.
A ---> B
C ---> B
B ---> D
B ---> E

For vertex B, the in-degree is 2 and the out-degree is 2.

9. Path

A path is a sequence of vertices connected by edges. 

A --- B --- C --- D

A → B → C → D is a path from A to D.

Paths are fundamental to graph algorithms because many problems involve finding whether one vertex can reach another or finding the shortest path between vertices.

10. Path Length

The path length is generally the number of edges used to travel from the starting vertex to the destination. 

A --- B --- C --- D

The path from A to D contains three edges, so its length is 3.

11. Walk, Trail, and Path

These terms describe different ways of moving through a graph.

  • Walk: A sequence of vertices and edges where vertices or edges may be repeated.
  • Trail: A walk where an edge is not repeated.
  • Path: A route where vertices are normally not repeated.

The exact terminology can vary slightly between textbooks, but these distinctions are useful when studying graph theory and algorithms.

12. Cycle

A cycle is a path that starts and ends at the same vertex without repeating the intermediate vertices. 

A --- B
|     |
D --- C

A → B → C → D → A forms a cycle.

13. Self-Loop

A self-loop is an edge that connects a vertex to itself. 

A ---> A

Self-loops are possible in many graph models, although some applications explicitly disallow them.

14. Connected Vertices

Two vertices are connected if there is a path between them. 

A --- B --- C

D --- E

A, B, and C are connected to each other through paths. D and E form a separate connected group.

15. Connected Graph

An undirected graph is connected when every vertex can reach every other vertex through some path. 

A --- B --- C
      |
      D

Every vertex in this graph can be reached from every other vertex, so the graph is connected.

16. Connected Component

A connected component is a maximal group of vertices in an undirected graph where every vertex can reach every other vertex in that group. 

A --- B --- C

D --- E

F

This graph contains three connected components: {A, B, C}, {D, E}, and {F}.

17. Weighted Edge

A weighted edge has a numerical value called its weight. The weight can represent distance, cost, time, capacity, or another measurable property. 

A --- 10 --- B
B --- 5 ---- C

The edge between A and B has weight 10, while the edge between B and C has weight 5.

18. Unweighted Graph

An unweighted graph treats edges as simple connections without numerical weights. 

A --- B --- C

Each edge represents a connection, but no distance or cost is assigned to it.

19. Dense and Sparse Graphs

Graphs can also be described by how many edges they contain relative to the maximum possible number of edges.

  • Dense graph: Contains a relatively large number of edges.
  • Sparse graph: Contains relatively few edges.

This distinction is important when choosing a graph representation. Sparse graphs are commonly represented efficiently using adjacency lists, while dense graphs can make adjacency matrices practical.

20. Degree of a Graph

For an undirected graph, the degree sequence describes the degrees of all vertices. The degree of an individual vertex tells us how many edges are incident to that vertex.

The sum of the degrees of all vertices in an undirected graph is twice the number of edges. This is commonly known as the handshaking principle.

21. Incident Edge

An edge is incident to a vertex when that edge is directly connected to the vertex. 

A --- B --- C

The edge A-B is incident to both A and B. The edge B-C is incident to both B and C.

22. Source and Destination

In a directed graph, an edge has a starting vertex called the source and an ending vertex called the destination. 

A ---> B

A is the source and B is the destination.

23. Subgraph

A subgraph is a graph formed from a subset of the vertices and edges of another graph.

Subgraphs are useful when analyzing a smaller portion of a larger network or when constructing specialized graph structures.

24. Complete Graph

A complete graph is a graph in which every pair of distinct vertices is directly connected by an edge. 

    A
   / \
  B---C

With three vertices, every vertex is connected directly to the other two.

25. Bipartite Graph

A bipartite graph can divide its vertices into two separate sets such that every edge connects a vertex from one set to a vertex in the other set.

Bipartite graphs are useful for modeling relationships such as students and courses, employees and projects, or users and products.

26. Tree

A tree is a connected undirected graph with no cycles. For a tree with V vertices, there are exactly V - 1 edges. 

      A
     / \
    B   C
   / \
  D   E

Trees are widely used for hierarchical data, searching, file systems, databases, and many algorithmic problems.

27. Graph Terminology at a Glance

Term Meaning
Vertex An individual node in a graph.
Edge A connection between vertices.
Adjacent vertices Vertices directly connected by an edge.
Degree Number of incident edges for a vertex in an undirected graph.
In-degree Number of directed edges entering a vertex.
Out-degree Number of directed edges leaving a vertex.
Path A sequence of connected vertices.
Cycle A route that starts and ends at the same vertex.
Connected graph Every vertex can reach every other vertex.
Connected component A maximal connected group within a graph.
Weighted edge An edge with an associated numerical value.
Self-loop An edge connecting a vertex to itself.

Why Graph Terminology Matters

Graph algorithms use these terms to describe the structure of a problem. For example, BFS and DFS explore neighboring vertices, Dijkstra's algorithm works with weighted edges, cycle detection looks for repeated routes, and topological sorting works with directed acyclic graphs.

When you understand vertices, edges, degree, paths, cycles, connectivity, and graph direction, algorithm descriptions become much easier to follow.

Common Mistakes to Avoid

  • Confusing a vertex with an edge.
  • Assuming a directed edge can automatically be traversed in both directions.
  • Confusing degree with the total number of vertices in a graph.
  • Assuming every graph is connected.
  • Confusing a path with a cycle.
  • Forgetting that edge weights can represent different quantities depending on the problem.
  • Using terminology for directed graphs, such as in-degree and out-degree, without considering edge direction.

Key Takeaways

  • A graph consists primarily of vertices and edges.
  • Edges may be directed or undirected and may optionally have weights.
  • Adjacent vertices are directly connected by an edge.
  • The degree of a vertex describes its connections.
  • A path represents a route through connected vertices.
  • A cycle returns to its starting vertex.
  • A connected graph allows every vertex to reach every other vertex.
  • Connected components divide a disconnected graph into connected groups.
  • Graph terminology provides the foundation for understanding graph traversal and graph algorithms.

Code Examples 

const graph = {
  A: ['B', 'C'],
  B: ['A', 'D'],
  C: ['A'],
  D: ['B']
};

console.log('Neighbors of A:', graph.A);
console.log('Neighbors of B:', graph.B);

console.log('Degree of A:', graph.A.length);
console.log('Degree of B:', graph.B.length);
    
const graph = {
  A: ['B', 'C'],
  B: ['D'],
  C: ['B'],
  D: []
};

const inDegree = {
  A: 0,
  B: 2,
  C: 1,
  D: 1
};

const outDegree = {
  A: 2,
  B: 1,
  C: 1,
  D: 0
};

console.log('B in-degree:', inDegree.B);
console.log('B out-degree:', outDegree.B);
    
const graph = {
  A: ['B'],
  B: ['A', 'C'],
  C: ['B', 'D'],
  D: ['C']
};

function hasPath(graph, start, target) {
  const visited = new Set();
  const queue = [start];

  while (queue.length > 0) {
    const current = queue.shift();

    if (current === target) {
      return true;
    }

    if (visited.has(current)) {
      continue;
    }

    visited.add(current);

    for (const neighbor of graph[current]) {
      if (!visited.has(neighbor)) {
        queue.push(neighbor);
      }
    }
  }

  return false;
}

console.log(hasPath(graph, 'A', 'D')); // true
console.log(hasPath(graph, 'A', 'X')); // false

Pro Tip

When learning graph algorithms, first identify the graph type: directed or undirected, weighted or unweighted, connected or disconnected. These properties often determine which algorithm and graph representation are appropriate.

🎨 IgKnight Docs

Master HTML, CSS, JS, Python, .NET and more with easy-to-follow lessons and practical code examples.

© 2025 IgKnight Learning Platform. All rights reserved.