Graphs

A graph is a collection of nodes that may or may not be connected to each other.

The nodes are actually called vertices, the connections between vertices are called edges.
So it’s made of vertices and edges, where vertices are nodes that might have values, for instance integer values, and the edges are connections, things that connect the nodes to one another.

Many things in life can be represented by graphs for example, an airport, a social network or a city map where locations are vertices and roads between locations are edges.

Important concepts in graphs.

• Graph Cycle

  Simply put occurs in a graph when three or more vertices in the graph are connected to form a closed loop
  

  Note that the definition of a graph cycle is sometimes broadened to include cycles of length two or one.
  For example a Wikipedia page where one link leads to different pages, but eventually you may end up on the page where you started.
  
  

• Acyclic graph

  A graph that has no cycles.
  
  

• Cyclic graph

  A graph that has at least one cycle.
  
  

• Directed Graph

  Meaning that edges are directed and can be traversed only in one direction which is specified.
  For example from some airports you can reach a different airport only in one direction.
  
  

• Undirected Graph

  A graph without directed edges, meaning that they can be traversed in both directions.
  For example a graph of friends would be probably undirected as one friend can reach one another.
  
  

• Connected Graph

  A graph is connected if there is some path between any two nodes in the graph, meaning every node is reachable from every other node.

  In case of a directed graph, the graph is:

  • strongly connected: if there are bidirectional connections between the vertices of every pair of vertices (i.e., for every vertex pair (x, y) you can reach y from x and x from y)
  • weakly connected: if replacing all directed edges with undirected edges produces a connected graph (i.e., the underlying undirected graph is connected, even though you may not be able to reach every vertex following only the edge directions)

  A graph that is not connected may be called disconnected.

Weighted vs Unweighted Graphs

Graphs can also be classified based on whether their edges carry values. In a weighted graph, each edge has an associated numerical value (a weight), which might represent distance, cost, capacity, or any other metric. In an unweighted graph, all edges are treated equally with no associated value. Algorithms like Dijkstra’s shortest path rely on edge weights, whereas BFS naturally finds shortest paths in unweighted graphs.

Graph Representations

Two primary ways to represent a graph in code are the adjacency list and the adjacency matrix.

• Adjacency List – each vertex stores a list of its neighbors. This is memory-efficient for sparse graphs (few edges relative to vertices) because it uses O(V + E) space, where V is the number of vertices and E is the number of edges. Checking whether a specific edge exists takes O(degree) time, where degree is the number of neighbors.

• Adjacency Matrix – a 2D array of size V x V where entry [i][j] indicates whether an edge exists between vertex i and vertex j (or the edge weight in a weighted graph). This uses O(V^2) space regardless of the number of edges, which makes it costly for sparse graphs but efficient for dense ones. The main advantage is O(1) edge lookup time.

Operation	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V^2)
Check edge exists	O(degree)	O(1)
Find all neighbors	O(degree)	O(V)
Add edge	O(1)	O(1)
Remove edge	O(degree)	O(1)

In practice, adjacency lists are the default choice for most graph problems because real-world graphs tend to be sparse.

Common Graph Algorithms

Several fundamental algorithms operate on graphs and are worth knowing:

• Breadth-First Search (BFS) – explores all neighbors at the current depth before moving deeper. Useful for finding the shortest path in unweighted graphs. Runs in O(V + E).
• Depth-First Search (DFS) – explores as far as possible along each branch before backtracking. Useful for cycle detection, topological sorting, and finding connected components. Also runs in O(V + E). You can read more about DFS here.
• Dijkstra’s Algorithm – finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights. Runs in O((V + E) log V) with a priority queue.
• Bellman-Ford Algorithm – finds shortest paths from a source vertex even when negative edge weights are present. Runs in O(V * E).
• Topological Sort – produces a linear ordering of vertices in a directed acyclic graph (DAG) such that for every directed edge (u, v), u comes before v.