Graph

Graph

Problem Description

Implement a Graph data structure that can represent relationships between vertices (nodes) using an adjacency list representation.

What is a Graph?

A graph is a non-linear data structure consisting of vertices (nodes) and edges (connections between vertices). Graphs can be directed or undirected, weighted or unweighted.

Characteristics

• Time Complexity:
  • Add vertex: O(1)
  • Add edge: O(1)
  • Remove edge: O(E) where E is number of edges from vertex
  • Check if edge exists: O(E)
• Space Complexity: O(V + E) where V is vertices and E is edges

Graph Types

1. Directed: Edges have direction (A → B)
2. Undirected: Edges are bidirectional (A ↔ B)
3. Weighted: Edges have weights/costs
4. Unweighted: All edges have same weight

Representation

Adjacency List (recommended):

Map<Integer, List<Edge>>
Vertex 1 → [2, 3, 4]
Vertex 2 → [1, 5]
Vertex 3 → [1]

Edge Structure:

• destination vertex
• weight (optional)

Your Task

Implement the following methods in Graph.java:

1. addVertex(int vertex) - Add a vertex
2. addEdge(int source, int dest, int weight) - Add weighted edge
3. addEdge(int source, int dest) - Add unweighted edge
4. removeEdge(int source, int dest) - Remove an edge
5. getNeighbors(int vertex) - Get all adjacent vertices
6. hasEdge(int source, int dest) - Check if edge exists
7. getAllVertices() - Get all vertices

Test Cases to Consider

• Add vertices and edges
• Directed vs undirected behavior
• Weighted edges
• Remove edges
• Check edge existence
• Get neighbors of a vertex
• Handle non-existent vertices
• Self-loops (vertex to itself)
• Multiple edges between same vertices

Hints

• Use HashMap<Integer, List<Edge>> for adjacency list
• For undirected graphs: add edges in both directions
• Consider creating an Edge class to store destination and weight
• Check if vertices exist before adding edges
• Handle null cases gracefully

Directed vs Undirected

Directed Graph:

addEdge(1, 2);  // Only 1 → 2

Undirected Graph:

addEdge(1, 2);  // Both 1 → 2 and 2 → 1

Common Graph Operations

1. Traversal: BFS, DFS
2. Shortest Path: Dijkstra, Bellman-Ford, Floyd-Warshall
3. Minimum Spanning Tree: Kruskal's, Prim's
4. Cycle Detection: DFS-based
5. Topological Sort: For DAGs
6. Connected Components: Union-Find

Applications

• Social networks (friends, followers)
• Maps and navigation (roads, cities)
• Computer networks (routers, connections)
• Dependency graphs (tasks, prerequisites)
• Web page links
• Recommendation systems

Follow-up Questions

1. How would you detect a cycle in your graph?
2. How would you find the shortest path between two vertices?
3. How would you determine if the graph is connected?
4. How would you implement graph coloring?
5. What's the difference between adjacency list and adjacency matrix?

Adjacency List vs Adjacency Matrix

Aspect	Adjacency List	Adjacency Matrix
Space	O(V + E)	O(V²)
Add Edge	O(1)	O(1)
Remove Edge	O(E)	O(1)
Check Edge	O(E)	O(1)
Best For	Sparse graphs	Dense graphs

Common Pitfalls

• Not handling directed/undirected correctly
• Forgetting to check if vertices exist
• Memory issues with dense graphs (use matrix instead)
• Not removing edges from both directions in undirected graphs

Graph Representations

1. Adjacency List: Map of vertex to list of neighbors (implemented here)
2. Adjacency Matrix: 2D array of edges
3. Edge List: List of all edges
4. Incidence Matrix: Matrix of vertices vs edges

Related Algorithms

• Depth First Search (DFS)
• Breadth First Search (BFS)
• Dijkstra's Algorithm
• Topological Sort
• Union-Find
• Minimum Spanning Tree

Practice Problems

1. Number of Islands
2. Course Schedule (topological sort)
3. Word Ladder
4. Network Delay Time
5. Clone Graph
6. Alien Dictionary