Graphs Implementation

Adjacency List Graph (25 points)

Create a class GraphAdjList.java:

public class GraphAdjList<T> {
    private Map<T, List<Edge<T>>> adjacencyList;
    private boolean isDirected;
    private boolean isWeighted;
    
    public class Edge<T> {
        T destination;
        int weight;
        Edge(T dest, int weight);
    }
    
    public GraphAdjList(boolean isDirected, boolean isWeighted);
    
    // Vertex operations
    public void addVertex(T vertex);
    public void removeVertex(T vertex);
    public boolean hasVertex(T vertex);
    public Set<T> getVertices();
    public int vertexCount();
    
    // Edge operations
    public void addEdge(T source, T destination);
    public void addEdge(T source, T destination, int weight);
    public void removeEdge(T source, T destination);
    public boolean hasEdge(T source, T destination);
    public int getWeight(T source, T destination);
    public int edgeCount();
    
    // Neighbor operations
    public List<T> getNeighbors(T vertex);
    public List<Edge<T>> getEdges(T vertex);
    public int inDegree(T vertex);   // For directed graphs
    public int outDegree(T vertex);  // For directed graphs
    public int degree(T vertex);     // For undirected graphs
}

Adjacency Matrix Graph (20 points)

Create a class GraphAdjMatrix.java:

public class GraphAdjMatrix {
    private int[][] matrix;
    private int vertexCount;
    private boolean isDirected;
    private boolean isWeighted;
    private static final int NO_EDGE = Integer.MAX_VALUE;
    
    public GraphAdjMatrix(int vertices, boolean isDirected, boolean isWeighted);
    
    // Edge operations
    public void addEdge(int source, int destination);
    public void addEdge(int source, int destination, int weight);
    public void removeEdge(int source, int destination);
    public boolean hasEdge(int source, int destination);
    public int getWeight(int source, int destination);
    
    // Neighbor operations
    public List<Integer> getNeighbors(int vertex);
    public int degree(int vertex);
    
    // Utility
    public int[][] getMatrix();
    public void printMatrix();
}

Space Comparison:

• Adjacency List: O(V + E) - better for sparse graphs
• Adjacency Matrix: O(V²) - better for dense graphs

Graph Traversals (15 points)

Add traversal methods to your graph classes:

// BFS - Breadth-First Search
// Returns vertices in level-order from source
public List<T> bfs(T source);

// DFS - Depth-First Search (iterative with stack)
public List<T> dfsIterative(T source);

// DFS - Depth-First Search (recursive)
public List<T> dfsRecursive(T source);

// Example:
//   0 --- 1
//   |     |
//   2 --- 3
//
// bfs(0): [0, 1, 2, 3]
// dfs(0): [0, 1, 3, 2] or [0, 2, 3, 1]

Shortest Path - Unweighted (15 points)

Find shortest paths in unweighted graphs using BFS:

// P4a: Shortest path between two vertices (unweighted)
// Returns the path as a list, or empty list if no path exists
public List<Integer> shortestPath(int[][] graph, int source, int destination);

// P4b: Shortest distances from source to all vertices
// Returns array where dist[i] = shortest distance from source to i
// -1 if unreachable
public int[] shortestDistances(int[][] graph, int source);

// P4c: Word Ladder - Transform word1 to word2
// Each step changes exactly one letter, all intermediate words must be valid
// wordList = ["hot","dot","dog","lot","log","cog"]
// beginWord = "hit", endWord = "cog"
// Output: 5 (hit → hot → dot → dog → cog)
public int wordLadder(String beginWord, String endWord, List<String> wordList);

Shortest Path - Weighted (20 points)

Implement classic shortest path algorithms:

// P5a: Dijkstra's Algorithm
// Returns shortest distances from source to all vertices
// Works for non-negative weights only
public int[] dijkstra(int[][] graph, int source);

// P5b: Bellman-Ford Algorithm
// Returns shortest distances from source to all vertices
// Works with negative weights, detects negative cycles
// Returns null if negative cycle exists
public int[] bellmanFord(int[][] edges, int vertices, int source);

// P5c: Find the path (not just distance) using Dijkstra
public List<Integer> dijkstraPath(int[][] graph, int source, int destination);

// Example graph (adjacency matrix with weights):
//     0   1   2   3
// 0 [ 0,  4,  0,  0]
// 1 [ 4,  0,  8,  0]
// 2 [ 0,  8,  0,  7]
// 3 [ 0,  0,  7,  0]
// dijkstra(graph, 0) → [0, 4, 12, 19]

Cycle Detection (15 points)

Detect cycles in graphs:

// P6a: Detect cycle in undirected graph
// Using DFS with parent tracking
public boolean hasCycleUndirected(int[][] graph);

// P6b: Detect cycle in directed graph
// Using DFS with coloring (white, gray, black)
public boolean hasCycleDirected(int[][] graph);

// P6c: Find all vertices in a cycle (if cycle exists)
public List<Integer> findCycleVertices(int[][] graph);

// Example:
// 0 → 1 → 2
//     ↑   ↓
//     └── 3
// hasCycleDirected → true (1 → 2 → 3 → 1)

Topological Sort (15 points)

Order vertices in a DAG:

// P7a: Topological sort using DFS
// Returns null if graph has a cycle
public List<Integer> topologicalSortDFS(int[][] graph);

// P7b: Topological sort using Kahn's algorithm (BFS)
// Returns null if graph has a cycle
public List<Integer> topologicalSortBFS(int[][] graph);

// P7c: Course Schedule - Can finish all courses?
// prerequisites[i] = [a, b] means must take b before a
// numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
// Output: true (order: 0, 1, 2, 3 or 0, 2, 1, 3)
public boolean canFinishCourses(int numCourses, int[][] prerequisites);

// P7d: Course Schedule II - Return order to take courses
public int[] findCourseOrder(int numCourses, int[][] prerequisites);

Connected Components (15 points)

Find connected regions in graphs:

// P8a: Count connected components in undirected graph
public int countComponents(int vertices, int[][] edges);

// P8b: Find all connected components (return list of component lists)
public List<List<Integer>> findComponents(int vertices, int[][] edges);

// P8c: Number of Islands
// grid[i][j] = 1 (land) or 0 (water)
// Count connected land regions (4-directional connectivity)
// [1,1,0,0]
// [1,1,0,0]
// [0,0,1,0]
// [0,0,0,1]
// Output: 3
public int numIslands(char[][] grid);

// P8d: Is graph bipartite? (can be 2-colored)
public boolean isBipartite(int[][] graph);

Union-Find / Disjoint Set (20 points)

Implement and use Union-Find data structure:

// P9a: Implement Union-Find with path compression and union by rank
public class UnionFind {
    private int[] parent;
    private int[] rank;
    private int components;
    
    public UnionFind(int n);
    public int find(int x);           // Find with path compression
    public void union(int x, int y);  // Union by rank
    public boolean connected(int x, int y);
    public int getComponents();
}

// P9b: Detect cycle in undirected graph using Union-Find
public boolean hasCycleUnionFind(int vertices, int[][] edges);

// P9c: Redundant Connection
// Find the edge that, when removed, makes tree (no cycles)
// edges = [[1,2],[1,3],[2,3]] → [2,3]
public int[] findRedundantConnection(int[][] edges);

// P9d: Number of Provinces
// isConnected[i][j] = 1 if cities i and j are connected
public int findCircleNum(int[][] isConnected);

Minimum Spanning Tree (20 points)

Find MST of weighted undirected graph:

// P10a: Kruskal's Algorithm
// Returns list of edges in MST
// Uses Union-Find for cycle detection
public List<int[]> kruskalMST(int vertices, int[][] edges);

// P10b: Prim's Algorithm
// Returns list of edges in MST
// Uses priority queue
public List<int[]> primMST(int[][] graph);

// P10c: Minimum cost to connect all cities
// Return -1 if impossible
public int minCostConnectCities(int n, int[][] connections);

// Example:
// Edges: [[0,1,10], [0,2,6], [0,3,5], [1,3,15], [2,3,4]]
// MST edges: [[2,3,4], [0,3,5], [0,1,10]]
// Total weight: 19

Advanced Graph Problems (20 points)

Challenging graph problems:

// P11a: Clone Graph
// Deep copy an undirected graph
public Node cloneGraph(Node node);

// P11b: All Paths from Source to Target (DAG)
// Find all paths from node 0 to node n-1
public List<List<Integer>> allPathsSourceTarget(int[][] graph);

// P11c: Network Delay Time
// How long for signal from source to reach all nodes?
// times[i] = [source, target, time]
// Return -1 if impossible
public int networkDelayTime(int[][] times, int n, int source);

// P11d: Cheapest Flights Within K Stops
// Find cheapest price with at most k stops
// Return -1 if no such route
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k);