1. Adjacency List Implementation

1.1 Java Implementation

public class Graph {
    public Map<Integer, Vertex> vertices;
    public Set<Edge> edges;

    public Graph() {
        vertices = new HashMap<>();
        edges = new HashSet<>();
    }
}

public class Vertex {
    public int id;
    public int inDegree;
    public int outDegree;
    public List<Vertex> neighbors;
    public List<Edge> adjacentEdges;

    public Vertex(int id) {
        this.id = id;
        this.inDegree = 0;
        this.outDegree = 0;
        this.neighbors = new ArrayList<>();
        this.adjacentEdges = new ArrayList<>();
    }
}

public class Edge {
    public int weight;
    public Vertex source;
    public Vertex destination;

    public Edge(int weight, Vertex source, Vertex destination) {
        this.weight = weight;
        this.source = source;
        this.destination = destination;
    }
}

public static Graph buildGraphFromTriplets(int[][] matrix) {
    Graph graph = new Graph();
    for (int[] triplet : matrix) {
        int from = triplet[0];
        int to = triplet[1];
        int weight = triplet[2];

        if (!graph.vertices.containsKey(from)) {
            graph.vertices.put(from, new Vertex(from));
        }
        if (!graph.vertices.containsKey(to)) {
            graph.vertices.put(to, new Vertex(to));
        }

        Vertex sourceVertex = graph.vertices.get(from);
        Vertex destVertex = graph.vertices.get(to);

        Edge newEdge = new Edge(weight, sourceVertex, destVertex);
        graph.edges.add(newEdge);

        sourceVertex.neighbors.add(destVertex);
        sourceVertex.adjacentEdges.add(newEdge);
        sourceVertex.outDegree++;
        destVertex.inDegree++;
    }
    return graph;
}

2. Topological Sorting

Topological sorting works on directed acyclic graphs (DAGs). The algorithm finds nodes with zero in-degree, removes them, and repeats until all nodes are processed. The order in which zero in-degree nodes are removed represents a valid topological order.

public static List<Vertex> topologicalSort(Graph graph) {
    Map<Vertex, Integer> inDegreeMap = new HashMap<>();
    Queue<Vertex> zeroInDegreeQueue = new LinkedList<>();

    for (Vertex vertex : graph.vertices.values()) {
        inDegreeMap.put(vertex, vertex.inDegree);
        if (vertex.inDegree == 0) {
            zeroInDegreeQueue.offer(vertex);
        }
    }

    List<Vertex> result = new ArrayList<>();

    while (!zeroInDegreeQueue.isEmpty()) {
        Vertex current = zeroInDegreeQueue.poll();
        result.add(current);

        for (Vertex neighbor : current.neighbors) {
            int updatedInDegree = inDegreeMap.get(neighbor) - 1;
            inDegreeMap.put(neighbor, updatedInDegree);

            if (updatedInDegree == 0) {
                zeroInDegreeQueue.offer(neighbor);
            }
        }
    }

    return result;
}

Cycle Detection: A graph has a cycle if the topological sort result contains fewer vertices than the original graph. This is useful for problems like course scheduling (LeetCode 207).

3. Minimum Spanning Tree (MST)

3.1 Definitions

A spanning tree is a connected subgraph that includes all vertices of the original graph with exactly (V-1) edges. Key properteis:

• A connected graph can have multiple spanning trees
• All spanning trees have the same number of vertices and edges
• Spanning trees contain no cycles
• Adding any edge to a spanning tree creates a cycle

A minimum spanning tree is the spanning tree with the smallest total edge weight. This applies only to weighted graphs.

3.2 Prim's Algorithm

Prim's algorithm works well for dense graphs. Time complexity: O(V²) with adjacency matrix, O(E log V) with binary heap.

public static class EdgeWeightComparator implements Comparator<Edge> {
    @Override
    public int compare(Edge a, Edge b) {
        return a.weight - b.weight;
    }
}

public static Set<Edge> primMST(Graph graph) {
    PriorityQueue<Edge> edgeHeap = new PriorityQueue<>(new EdgeWeightComparator());
    Set<Edge> mstEdges = new HashSet<>();
    Set<Vertex> visitedVertices = new HashSet<>();

    for (Vertex vertex : graph.vertices.values()) {
        if (!visitedVertices.contains(vertex)) {
            visitedVertices.add(vertex);

            for (Edge edge : vertex.adjacentEdges) {
                edgeHeap.offer(edge);
            }

            while (!edgeHeap.isEmpty()) {
                Edge minEdge = edgeHeap.poll();
                Vertex targetVertex = minEdge.destination;

                if (!visitedVertices.contains(targetVertex)) {
                    visitedVertices.add(targetVertex);
                    mstEdges.add(minEdge);

                    for (Edge adjacentEdge : targetVertex.adjacentEdges) {
                        edgeHeap.offer(adjacentEdge);
                    }
                }
            }
        }
    }

    return mstEdges;
}

Note: The outer loop handles disconnected graphs (minimum spanning forest).

3.3 Kruskal's Algorithm

Kruskal's algorithm uses Union-Find to detect cycles. Time complexity: O(E log E).

public static class UnionFind {
    private Map<Vertex, Vertex> parent = new HashMap<>();
    private Map<Vertex, Integer> rank = new HashMap<>();

    public void initialize(Collection<Vertex> vertices) {
        for (Vertex v : vertices) {
            parent.put(v, v);
            rank.put(v, 0);
        }
    }

    public Vertex find(Vertex x) {
        if (!parent.get(x).equals(x)) {
            parent.put(x, find(parent.get(x)));
        }
        return parent.get(x);
    }

    public void union(Vertex x, Vertex y) {
        Vertex rootX = find(x);
        Vertex rootY = find(y);

        if (rootX.equals(rootY)) return;

        if (rank.get(rootX) < rank.get(rootY)) {
            parent.put(rootX, rootY);
        } else if (rank.get(rootX) > rank.get(rootY)) {
            parent.put(rootY, rootX);
        } else {
            parent.put(rootY, rootX);
            rank.put(rootX, rank.get(rootX) + 1);
        }
    }

    public boolean isConnected(Vertex x, Vertex y) {
        return find(x).equals(find(y));
    }
}

public static Set<Edge> kruskalMST(Graph graph) {
    UnionFind uf = new UnionFind();
    uf.initialize(graph.vertices.values());

    PriorityQueue<Edge> sortedEdges = new PriorityQueue<>(new EdgeWeightComparator());
    for (Edge edge : graph.edges) {
        sortedEdges.offer(edge);
    }

    Set<Edge> mstEdges = new HashSet<>();

    while (!sortedEdges.isEmpty()) {
        Edge currentEdge = sortedEdges.poll();

        if (!uf.isConnected(currentEdge.source, currentEdge.destination)) {
            mstEdges.add(currentEdge);
            uf.union(currentEdge.source, currentEdge.destination);
        }
    }

    return mstEdges;
}

4. Dijkstra's Shortest Path Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights.

public static Map<Vertex, Integer> shortestPath(Vertex source) {
    Map<Vertex, Integer> distance = new HashMap<>();
    Set<Vertex> processed = new HashSet<>();

    distance.put(source, 0);

    Vertex current = getMinimumUnprocessedVertex(distance, processed);

    while (current != null) {
        int currentDistance = distance.get(current);

        for (Edge edge : current.adjacentEdges) {
            Vertex neighbor = edge.destination;
            int newDistance = currentDistance + edge.weight;

            if (!distance.containsKey(neighbor)) {
                distance.put(neighbor, newDistance);
            } else {
                distance.put(neighbor, Math.min(distance.get(neighbor), newDistance));
            }
        }

        processed.add(current);
        current = getMinimumUnprocessedVertex(distance, processed);
    }

    return distance;
}

private static Vertex getMinimumUnprocessedVertex(
        Map<Vertex, Integer> distance, 
        Set<Vertex> processed) {

    int minDist = Integer.MAX_VALUE;
    Vertex minVertex = null;

    for (Map.Entry<Vertex, Integer> entry : distance.entrySet()) {
        Vertex vertex = entry.getKey();
        int dist = entry.getValue();

        if (!processed.contains(vertex) && dist < minDist) {
            minDist = dist;
            minVertex = vertex;
        }
    }

    return minVertex;
}

Optimization: The naive selection can be replaced with a custom min-heap that supports decrease-key operations for better performance.

Limitation: Dijkstra's algorithm does not work corectly when negative edge weights exist, as it assumes distances can only decrease.