Blog
Mert Özen's blog posts on software development, backend, frontend, and DevOps.
Union-Find and Minimum Spanning Trees: Building Networks with Kruskal
With path compression and union by rank, Union-Find answers "are these two elements in the same group?" in practically constant time; the naive version is 4,300 times slower on a long chain. We write a DisjointSet in C#, merge duplicate customer accounts through shared e-mails and phones, build the cheapest fiber network between offices with Kruskal, and confirm the result with Prim.
Shortest Paths: Dijkstra, PriorityQueue and a Brief Look at A*
Dijkstra finds the cheapest path in a graph with non-negative weights: with lazy deletion, since PriorityQueue has no decrease-key, in O((V + E) log V). We trace Dijkstra step by step on an intercity shipping network, reconstruct the path, show the wrong result with a negative weight and Bellman-Ford, and measure A* finding the same path on a 200 × 200 warehouse grid with 1,845 cells instead of 33,600.
Topological Sort and Cycle Detection: Dependency Order and Kahn's Algorithm
Topological sort orders the vertices of a DAG so that every dependency comes before its dependents, in O(V + E); Kahn's algorithm uses in-degrees and a queue, DFS uses three colors. We write both in C#, produce seed data and build orders, report the cycle path, and show with real output that EF Core uses the same algorithm in SaveChanges and how the DI container reports a circular dependency.
Graph Basics: Adjacency Lists, BFS and DFS Traversal
Sparse graphs are kept as adjacency lists and BFS finds the fewest steps in O(V + E); on a 5,000-vertex graph BFS over an adjacency matrix is 46 times slower. We write a generic Graph, BFS distances and paths, recursive and iterative DFS, connected components and a grid flood fill in C#, and show with real output that marking visited on dequeue makes 2 million enqueues instead of 2,000.