Graphs are composed of vertices (or nodes) connected by edges. Unlike trees, graphs can include cycles and vertices can be connected to any number of other vertices. This allows for a more complex network of connections to represent relationships.

Graph operations encompass adding and removing vertices or edges, checking for connectivity, and finding paths or cycles. Here's everything you can do with graphs and their time complexities:

The Inverse Ackermann function, denoted as a(n), is a math function that occurs in certain algorithms involving disjoint set unions or connectivity checks in graphs. The Inverse Ackermann function grows very slowly so when algorithms have a complexity of O(a(n)) it means that these algorithms are almost as efficient as running in constant time.

Graphs are made up of vertices and edges. Vertices represent nodes in a graph, each can containing values (or data), while edges are connections between these nodes, defining the connections among them. Vertices maintain a list of their adjacent neighbors, which are other nodes directly connected to them through edges:

Vertices are adjacent if there is an edge directly connecting them. A path in a graph is a sequence of vertices where each consecutive vertex is connected by an edge. Cycles are paths that start and end at the same vertex:

Another important aspect of graphs is weight. In weighted graphs, edges have weights assigned to them, which can represent quantities like distance, cost, or capacity. This allows for algorithms that find the shortest path or create a minimum spanning tree.

A connected component is a portion of the graph where vertices are connected by paths. In directed graphs, a strongly connected component is where every vertex is reachable from every other vertex in the component.

Graph directionality is when edges have a direction (directed graphs) or not (undirected graphs). In directed graphs, edges indicate a one-way relationship, while in undirected graphs, edges represent a two-way, mutual connection.

Adjacency lists are a way to represent graphs, where each vertex stores a list of other vertices directly connected by edges. Typically implemented as a hashmap, where keys are vertices and values are a list of adjacent vertices. This structure is a flexible way to represent the relationships within the graph.

Adjacency lists are typically built from a given list of edges, where each edge in the list is represented as a pair of vertices indicating an edge from one vertex to another. Each edge is a list containing two items: the source vertex and the destination vertex.

A matrix is a two-dimensional array that forms a rectangle of cells, organized into rows and columns. The individual items in a matrix are called elements or cells. The dimensions of a matrix are defined by the number of rows and columns it contains. A matrix with m rows and n columns is called a m × n matrix:

In graph theory, an adjacency matrix is a way to represent connections between nodes in a graph. It always forms a square matrix where each element indicates whether a pair of vertices is directly connected by an edge. The rows and columns correspond to the vertices of the graph.

Adjacency matrices are extremely inefficient and should be avoided. They consume a large amount of memory to store many zero values, which represent absent edges between most pairs of vertices. Operations like adding or removing can be computationally expensive because we need to resize and update large portions of the matrix. Use adjacency lists.

Graph traversal algorithms, such as Depth-First Search (DFS) and Breadth-First Search (BFS), are necessary for exploring graphs. Understanding how to implement and apply these algorithms for different graph representations—specifically, adjacency lists and matrices—is important for graph problems.

DFS for Adjacency Lists: DFS explores as far as possible along one branch before backtracking. This is implemented using recursion (or a stack). In adjacency lists, DFS begins at a selected node, marking it as visited using a hashset. It then recursively visits unvisited neighboring nodes, exploring the graph's depth before backtracking to explore new branches:

BFS for Adjacency Lists: BFS explores the graph level by level, starting from a selected node. It uses a queue to keep track of the order in which to visit nodes. For adjacency lists, BFS visits each unvisited neighbor of a node, marks it as visited, and adds its adjacent nodes to the queue. This process is repeated until the queue is empty, so that all connected nodes are visited in increasing distance from the starting node:

DFS for Matrices: DFS selects an unvisited node and explores as far along a branch as possible, similar to the process with adjacency lists. However, instead of iterating over a list of neighbors, the algorithm checks the matrix in all four directions to find the next unvisited node to explore:

BFS for Matrices: BFS starts from a given cell (or node) and explores all its neighboring cells first, before moving to the next level. To implement BFS on a matrix, we typically use a queue to keep track of the cells to visit (implemented using hashset) next:

Graphs are incredibly flexible data structures that can represent complex relationships which is why they are popular in coding interviews. Here are some essential tips and tricks for solving graph-related questions: