🚀 Blog 10: Advanced Graph Tricks & Real-World Applications

Graphs form the backbone of network design, routing, compilers, scheduling, recommendation systems, DNA sequencing, and even blockchain. Beyond BFS/DFS, shortest paths, and MST, there are deeper tricks and problems every engineer should know.

This blog brings together advanced graph concepts, interview classics, and real-world applications.

🧭 1. Eulerian Path & Circuit

Eulerian Path: Visits every edge exactly once.
Eulerian Circuit: A path that starts and ends at the same vertex, visiting every edge once.

Condition:

Eulerian Path exists if 0 or 2 vertices have odd degree.
Eulerian Circuit exists if all vertices have even degree.

🔹 Application:

Route planning (postman problem).
DNA sequencing (finding Eulerian paths in De Bruijn graphs).

Java Snippet:

public boolean hasEulerianCircuit(int V, List<List<Integer>> adj) {
    for (int i = 0; i < V; i++) {
        if (adj.get(i).size() % 2 != 0) return false;
    }
    return true;
}

🧩 2. Hamiltonian Path & Cycle

Hamiltonian Path: Visits every vertex exactly once.
Hamiltonian Cycle: Path that starts and ends at the same vertex, visiting all vertices once.

Difference vs. Eulerian:

Eulerian → covers edges.
Hamiltonian → covers vertices.

🔹 Application:

Traveling Salesman Problem (TSP).
Bioinformatics (DNA assembly).

Backtracking Template:

boolean hamiltonianPath(int[][] graph, int pos, boolean[] visited, int count) {
    if (count == graph.length) return true;

    for (int v = 0; v < graph.length; v++) {
        if (graph[pos][v] == 1 && !visited[v]) {
            visited[v] = true;
            if (hamiltonianPath(graph, v, visited, count + 1)) return true;
            visited[v] = false;
        }
    }
    return false;
}

🧮 3. Graph Compression (Heavy-Light Decomposition, Centroid Decomposition)

Heavy-Light Decomposition (HLD): Breaks trees into heavy paths + light edges → useful for LCA queries, range queries on paths.
Centroid Decomposition: Recursive decomposition of tree → useful in divide-and-conquer algorithms on trees.

🔹 Applications:

Dynamic programming on trees.
Network routing optimization.

⚡ 4. Graph Coloring

Assign colors to vertices so no two adjacent vertices share the same color.
NP-Complete for general graphs, but greedy approximations work.

🔹 Applications:

Register allocation in compilers.
Timetable scheduling.
Map coloring.

Greedy Example:

public int[] graphColoring(int V, List<List<Integer>> adj) {
    int[] result = new int[V];
    Arrays.fill(result, -1);
    result[0] = 0;

    boolean[] available = new boolean[V];
    for (int u = 1; u < V; u++) {
        Arrays.fill(available, true);

        for (int v : adj.get(u)) {
            if (result[v] != -1) available[result[v]] = false;
        }

        int color;
        for (color = 0; color < V; color++) if (available[color]) break;
        result[u] = color;
    }
    return result;
}

🌍 5. Real-World Applications of Graph Theory

Web & Social Networks

PageRank (Google search) = graph centrality.
Friend recommendation = shortest path / bipartite matching.

Networking & Routing

Shortest path algorithms power IP routing (Dijkstra in OSPF, Bellman-Ford in RIP).

Scheduling & Dependency Management

Topological sort in build systems (Maven/Gradle).
Task scheduling in cloud platforms.

Transport & Logistics

Eulerian paths for garbage collection/postal delivery.
Hamiltonian cycles for TSP in supply chain.

Biology & Chemistry

Protein interaction networks.
DNA sequencing with Eulerian paths.

Cybersecurity & Blockchain

Strongly connected components for vulnerability detection.
Graph compression for transaction flow analysis.

📊 Complexity Snapshot

Problem	Complexity
Eulerian Path/Circuit	O(V+E)
Hamiltonian Path/Cycle	NP-Complete
Graph Coloring	NP-Hard (Greedy: O(V+E))
HLD Queries	O(log² N)
Centroid Decomposition	O(N log N)