Implement a Graph (Adjacency Matrix)

To design a graph using an adjacency matrix, I would start by initializing a 2D integer array of size V x V, where V is the number of vertices. Each cell [i][j] will store the weight of the edge from node i to j; if no edge exists, we can store infinity or zero depending on the problem context. For the addEdge method, if the graph is directed, I simply assign the weight to matrix[source][destination]. If undirected, I update both matrix[source][destination] and matrix[destination][source] to maintain symmetry. This operation runs in constant time, O(1). To check for a path, I would use Breadth-First Search since we need the shortest unweighted path or just reachability. I'll initialize a queue with the starting node and a boolean array to track visited nodes. While the queue isn't empty, I dequeue a node and iterate through its entire row in the matrix. For every column index representing a neighbor, if an edge exists and the neighbor hasn't been visited, I mark it visited and enqueue it. If I encounter the destination node during this process, I return true immediately. If the queue empties without finding the target, the path doesn't exist. This approach ensures O(V^2) time complexity due to the matrix iteration, which is acceptable for dense graphs typical in internal recommendation systems where connectivity is high.