A vertex is a fundamental unit of a graph that represents an entity, object, or data point. It is where edges originate or terminate.
An edge is a connection between two vertices that represents a relationship, communication path, or interaction. Edges can be directed (with direction) or undirected.
The degree of a vertex is the number of edges connected to it.
In undirected graphs: total number of edges incident to the vertex.
In directed graphs:
Adjacency List: An Adjacency List representation technique widely used in computer science, networking, and industry-grade applications, espicially the graph is sparse (few edges relative to nodes).
An Adjacency List represents a graph G = (V, E) as a collection of lists or arrays, where each vertex v ∈ V maintains a list of all adjacent vertices (i.e., all the vertices directly connected to v by an edge).
{
A : [B, C, D],
B : [A],
C : [A],
D : [A]
}
Adjacency List
{
A: [{node: 'B', weight: 5}, {node: 'C', weight: 2}],
B : [],
C : [{node: 'B', weight: 1}]
}
An adjacency list is a space-efficient data structure used to represent graphs. Its particular useful in real-world scenarios involving sparse graphs, where the number of edges is much less than the square of the number of vertices. It is used across various domains in industry.
| Domain | Use Case | Explanation |
|---|---|---|
| Networking | Routing protocols (e.g., OSPF, BGP) | Routers maintain a map of the network (nodes as routers, edges as links). Adjacency lists efficiently store which routers are directly connected. |
| Social Networks | Friend/follow relationships | Platforms like Facebook or Twitter use adjacency lists to represent users (nodes) and their connections (edges). Efficient for querying mutual friends, suggestions, etc. |
| Search Engines | Web page linking (PageRank) | The web is a massive graph of pages (nodes) and links (edges). Adjacency lists allow efficient traversal and ranking. |
| Recommendation Engines | Collaborative filtering | Users and products can be modeled as a bipartite graph; adjacency lists help in recommending based on neighborhood traversal. |
| Compiler Design | Control Flow Graphs | Nodes represent statements/blocks; edges represent flow of control. Used in optimization and static analysis. |
| Transportation & Logistics | Maps, GPS, delivery optimization | Cities/locations as nodes and roads as edges. Adjacency lists enable quick route finding (e.g., using Dijkstra or A*). |
| Game Development | Pathfinding in maps | Maps are often modeled as grids or graphs. Adjacency lists help in implementing efficient pathfinding algorithms like A*. |
| Telecom | Call graphs, connectivity checks | Represents call traffic, connections between subscribers or towers. |
| Cybersecurity | Network attack graphs, privilege escalation paths | Security tools model systems as graphs to detect vulnerabilities. |
An Adjacency Matrix is a square matrix used to represent a finite graph, where the rows and columns correspond to the graph's vertices, and the values in the matrix indicate the presence, direction and weight of edges between the vertices.
For unweighted graphs:
For weighted graphs:
| Adjacency Matrix | A(0) | B(1) | C(2) |
|---|---|---|---|
| A | 0 | 1 | 1 |
| B | 0 | 0 | 0 |
| C | 0 | 1 | 0 |
Unweighted Directed Graph
A -> B
A -> C
C -> B
| Adjacency Matrix | A | B | C |
|---|---|---|---|
| A | 0 | 5 | 2 |
| B | 0 | 0 | 0 |
| C | 0 | 1 | 0 |
Weighted Directed Graph
A -> B (5)
A -> C (2)
C -> B (1)
An adjacency matrix is widely used in industry settings where fast edge lookup, dense graph representation and matrix-based computation are needed. it is especially powerful in systems that process graphs using linear algebra, parallel computing or GPU acceleration.
| Domain | Application |
|---|---|
| Machine Learning / AI | Graph Neural Networks (GNNs), attention models, spectral clustering |
| Computer Vision | Image segmentation using region adjacency graphs (RAGs) |
| Social Networks | Representing relationships, influence propagation models |
| Network Security | Attack path graphs, privilege escalation maps |
| Telecommunication | Full-mesh connectivity in routers and data centers |
| Bioinformatics | Protein interaction networks, gene regulatory networks |
| Physics / Simulations | Modeling energy transfer, quantum systems using adjacency matrices |
| Recommendation Systems | Item-item or user-user interaction graphs |
| Graph Theory Research | Analyzing spectral properties (e.g., eigenvalues of the adjacency matrix) |
| Robotics / Path Planning | Grid-based maps for navigation (A* or Dijkstra in dense graphs) |
A bipartite graph is a graph whose vertex set can be divided into two disjoint sets (say U and V) such that every edge connects a vertex from U to a vertex from V.
U = {A, B}
V = {1, 2}
Edges = { (A-1), (A-2), (B-1)}
All edges go from a node in U to a node in V.
Applications:
A complete graph is a graph in which every pair of distinct vertices is connected by a unique edge.
It is denoted as Kn, where n is the number of vertices.
K3 -
Properties:
Applications:
A tree is a special type of connected, acyclic undirected graph.
Properties
Applications:
1. Design and implement a function that constructs the adjacency list representation for a graph.
The graph can be one of the following types:
Given the Input Parameters as:
Return an adjacency list where each node index maps to an array of its connected nodes.
| Parameter \ Case | Undirected, Unweighted Graph | Directed Weighted Graph | Undirected Weighted Graph | Directed Unweighted Graph |
|---|---|---|---|---|
| n | n = 4 |
n = 4 | n = 4 | n = 4 |
| edges | [0 1] [0 2] [1 2] [2 3] | [0 1 5] [0 2 10] [1 3 3] | [0 1 5] [1 2 3] [2 3 2] [3 0 4] | [0 1] [0 2] [1 3] [2 3] |
| Function call | buildAdjacencyList(n, edges, {directed: false, weighted: false}); | buildAdjacencyList(n, edges, {directed: true, weighted: true}); | buildAdjacencyList(n, edges, { directed: false, weighted: true }) | buildAdjacencyList(n, edges, { directed: true, weighted: false }) |
2. Given a graph represented as an adjacency list, The graph may be either directed or undirected, but all edges are unweighted. Your task is to design and implement two functions:
Functions should return the list of nodes in the order they are visited, starting from a given start node.
| Parameter \ Case | Best Case (Linear Path) | Worst Case (Complete Graph) | Edge Case (Single Node) |
|---|---|---|---|
| Input | n = 4 edges = [0 1] [0 2] [1 3] [2 3], adjList = [[1,2],[0,3],[0,3],[1,2]] start = 0 |
n = 4 edges = [0 1] [0 2] [0 3] [1 2] [1 3] [2 3], adjList = [[1,2,3],[0,2,3],[0,1,3],[0,1,2]] start = 0 | n = 1 adjList = [[]] start = 0 |
| DFS Output | [0, 1, 2, 3] | [0, 1, 2, 3] (order varies by neighbor ordering) | [0] |
| BFS Output | [0, 1, 3, 2] | [0, 1, 2, 3] | [0] |
| Explanation | Each node has only one neighbor → traversal is straightforward | All nodes are directly connected, so BFS visits all at depth 1 and DFS can vary | Only one node, no traversal needed |
3. Given a graph represented as an adjacency list, along with the total number of nodes n and a list of edges. Design an algorithm that determines whether the graph contains a cycle.
The graph can be either directed or undirected.
Implement solutions for: Undirected Graphs & Directed Graphs.
The algorithm should return true if a cycle exists, otherwise false.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | n = 5, edges = [[0,1],[1,2]], isDirected=false | n = 5, edges = [[0,1],[1,2],[2,0]], isDirected=true | n = 1, edges = [], isDirected=true/false |
| Output | false (no cycles) | true (a cycle exists in a directed graph) | false (1 node, no edges, no cycle) |
| Explanation | Graph is a simple line — no backtracking or cycles | DFS traverses nodes, revisits ancestor in recursion stack | Single node — cycle not possible without 2+ nodes |
4. Given 'n' nodes labeled 0 to n - 1 and a list of edges where each edge is a pair of [u, v] representing an undirected graph. Design an algorithm that return a list of all connected components.
Each component should be represented as a list of node labels.
The result can be returned in any order.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | n = 5, edges = [[0,1],[1,2],[3,4]] | n = 1000, fully connected graph | n = 1, edges = [] |
| Output | [[0,1,2], [3,4]] | [[0,1,2,...,999]] | [[0]] |
| Explanation | Two components: nodes 0-2 and 3-4 | All nodes form a single giant component | One node, no edges — one trivial componen |
5. Given an integer 'n' representing the total number of tasks labeled 0 to n-1. A list of directed edges 'edges', where each edge [u, v] indicates that task u must be completed before task v (i.e., u -> v).
Design an algorithm that returns a valid order to complete all tasks that satisfies these dependencies.
If it is impossible to complete all tasks due to a cycle (i.e., circular dependency), return an empty array [].
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | n = 4, edges = [[0,1],[1,2],[2,3]] | n = 5, edges = [[0,1],[1,2],[2,3],[3,4],[4,0]] | n = 1, edges = [] |
| Output | [0, 1, 2, 3] | [] | [0] |
| Explanation | No cycles, one straight valid path | Cycle detected (0→1→2→3→4→0), invalid task schedule | One task, no dependency, always valid |
6. Given an undirected graph represented as an adjacency list, where graph[i] contains a list of nodes adjacent to node i.
Design an algorithm to determine if the graph is bipartite - that is, if it is possible to split all the nodes into two groups such that no two nodes with in the same group are directly connected.
The algorithm should return true if such a split is possible, otherwise return false.
| Parameter \ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | [[1], [0, 2], [1]] | [[1], [0, 2], [1, 3], [2, 0]] | [[]] (graph with a single node and no edges) |
| Output | true | false | true |
| Explanation | Simple linear graph: 2-colorable | Contains an odd cycle: cannot be 2-colored | No edges: trivially bipartite |
7. Given an unweighted undirected graph with n nodes labeled from 0 to n - 1, and an array of edges, where each edge is a pair [u, v] representing an undirected connection between nodes u and v.
Design an algorithm that returns the shortest path distance from a given source node to every other node in the graph.
The graph is unweighted, so the shortest path is defined by the minimum number of edges between two nodes.
| Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Input Graph | Linear graph: 0–1–2–3–...–n-1 | Dense graph or large chain with max depth | No edges, or isolated nodes |
| Edges | [[0,1], [1,2], ..., [n-2, n-1]] | Dense mesh: many interconnected edges | [] |
| Output Dist[] | [0,1,2,3,...] | Increasing levels of distance or all 1s from center | [0, -1, -1, ...] if only source is reachable |
| Explanation | Source has a direct path to all nodes | Traversal visits all n nodes with BFS from source | Nodes are disconnected, BFS cannot reach them |
1. Given a weighted, directed graph represented by n nodes (numbered from 0 to n - 1) and a list of edges, where each edge is represented as a triple (u, v, w) indicating an edge from node u to node v with weight w.
Given a starting node start.
Design an algorithm that computes the shortest path distance from the start node to all other nodes in the graph.
Return an array dist where dist[i] represents the shortest distance from start to node i. If a node is unreachable, set the distance to -1.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | Linear graph or star graph | Dense graph with O(n²) edges | Graph with unreachable nodes, or no edges at all |
| Output | Shortest paths found quickly | Every node must be visited and updated multiple times | Unreachable nodes correctly marked with -1 |
| Explanation | Minimal operations, fewer updates needed | Frequent priority queue updates and distance re-evaluations | Algorithm must avoid infinite loops and handle disconnected components |
2. Given an undirected, connected graph with n nodes labeled from 0 to n - 1 and a list of edges, where each edge is represented as a tuple (u, v, w) - an edge between nodes u and v with weight w.
Design an algorithms to construct a Minimum Spanning Tree (MST) of the graph - a subset of edges that connects all vertices with the minimum possible total edge weight and no cycles.
Return the total weight of the MST.
A Minimum Spanning Tree is a fundamental concept in graph theory, especially for connected undirected, weighted graphs.
A minimum spanning tree of a connected, undirected graph is a subset of edges that:
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | n = 2 edges = [(0, 1, 1)] | n = 1000 edges = Complete graph, all combinations with varied weights | n = 1 edges = [] |
| Output | 1 | Depends on edge weights (but computed correctly) | 0 |
| Explanation | Only one edge, trivially forms the MST | Algorithm must process many edges (O(E log E)) | No edges; only one node – no tree required |
3. Given n tasks labeled from 0 to n - 1, and a list of directed edges where each edge (u, v) represents a dependency such that task u must be completed before task v.
The algorithm should
If there is a cycle in the graph, it is not possible to complete all tasks, and you should return an empty list.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | n = 3 edges = [(0, 1), (1, 2)] | n = 1000 edges = Every task depends on many others in a long chain (e.g. [(0,1), (1,2), ..., (998, 999)]) + cycle | n = 1 edges = [] |
| Output | [0, 1, 2] | If cycle: [], else large valid ordering | 0 |
| Explanation | Simple linear order, no cycles | Complex graph with long dependency chains; may require full traversal to detect cycles | Only one task, no constraints |
4. Given a 2D grid consisting of '1's(land) and '0's (water).
An island is formed by connecting adjacent lands horizontally or vertically.
Design an algorithm that counts and return the number of distinct islands in the grid.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | Grid Size : Small (e.g. 2×2) All '0's (no land), or all '1's (one island) | Grid Size : Large grid (e.g. 1000×1000) Alternating land and water forming many separate small islands | Grid Size: 0×0 grid or 1×1 grid All '0', or all '1' |
| Output | 0 (all water) or 1 (all land) | Up to rows × cols / 2 islands in checkerboard pattern | 0 or 1 |
| Explanation | No DFS/BFS required or just one traversal | Each land cell triggers DFS, many components to track | Must handle empty or single-cell grid |
5. Given a bipartite graph consisting of two disjoint sets of nodes: U and V, and a list of directed edges that connect nodes from U to nodes in V.
In a bipartite graph, the set of all vertices is divided into two disjoint sets:
Design an algorithm that computes the maximum matching - the largest set of edges such that no node in u or v is part of more than one edge in the matching.
A maximum matching in a graph is a matching that contains the largest possible number of edges, such that no two edges share a common vertex.
Return the maximum number of pairwise-disjoint matches possible.
| Parameter\ Case | Best Case | Worst Case | Edge Case |
|---|---|---|---|
| Parameters | U an V size: Small, e.g., 2 and 2 edges: Full connectivity (e.g., complete bipartite) | U an V size: Large sets, e.g., 1000 and 1000 edges: Sparse or poorly connected graph | U an V size: One or both sets are empty edges: No edges at all |
| Output | Equal to min(len(U), len(V)) | Small or zero (if no feasible matches) | 0 |
| Explanation | All nodes can be perfectly matched | Many nodes cannot be matched due to disconnected structure | No match possible if no edges exist |