DFS and minimum spanning trees

Hazırlık: BFS’de kenar türleri

Claim: in a BFS of an undirected graph, every edge is either a tree edge (it discovered a vertex) or a cross edge (joining two vertices neither of which is an ancestor of the other). Why: if edge (x, y) joined an ancestor x to a descendant y two or more levels down, then x was processed before y’s parent, and x’s edge to y would have discovered y first, making (x, y) a tree edge. So non-tree edges only join vertices at the same level or adjacent levels, and those are cross edges.

İddia: Yönsüz bir çizgenin BFS’sinde her kenar ya ağaç kenarıdır (bir tepeyi keşfetmiştir) ya da çapraz kenardır (hiçbiri diğerinin atası olmayan iki tepeyi birleştirir). Nedeni: (x, y) kenarı, x atasını iki veya daha fazla düzey aşağıdaki y torununa bağlasaydı x, y’nin ebeveyninden önce işlenmiş olurdu. x’ten y’ye giden kenar y’yi önce keşfeder ve (x, y) bir ağaç kenarı olurdu. Dolayısıyla ağaç dışı kenarlar yalnızca aynı düzeydeki veya komşu düzeylerdeki tepeleri birleştirir; bunlar çapraz kenarlardır.

DFS

DFS has a tidy recursive form; the recursion itself acts as the stack, so no explicit stack is needed. It records an entry time when a vertex is discovered and an exit time when it is finished, using a global clock:

DFS’nin düzenli bir özyinelemeli biçimi vardır; özyinelemenin kendisi yığın görevini üstlenir, dolayısıyla ayrıca açık bir yığın gerekmez. Küresel bir saat kullanarak bir tepe keşfedildiğinde giriş zamanını, tamamlandığında ise çıkış zamanını kaydeder:

dfs(G, v):
    discovered[v] = true
    time = time + 1; entry_time[v] = time
    process_vertex_early(v)
    for each edge (v, y):
        if not discovered[y]:
            parent[y] = v
            process_edge(v, y)
            dfs(G, y)
        else if (not processed[y] and parent[v] != y) or G is directed:
            process_edge(v, y)
    process_vertex_late(v)
    time = time + 1; exit_time[v] = time
    processed[v] = true

dfs(G, v):
    discovered[v] = true
    time = time + 1; entry_time[v] = time
    process_vertex_early(v)
    for her (v, y) kenarı:
        if not discovered[y]:
            parent[y] = v
            process_edge(v, y)
            dfs(G, y)
        else if (not processed[y] and parent[v] != y) or G yönlü ise:
            process_edge(v, y)
    process_vertex_late(v)
    time = time + 1; exit_time[v] = time
    processed[v] = true

The condition parent[v] != y stops an undirected tree edge from being reported a second time when we look back at our own parent. A global finished flag (omitted above) lets a search stop early once it has found what it wanted.

parent[v] != y koşulu, kendi ebeveynimize geri baktığımızda yönsüz bir ağaç kenarının ikinci kez bildirilmesini engeller. Küresel finished bayrağı (yukarıda gösterilmemiştir), aramanın aradığını bulduğunda erken sonlanmasını sağlar.

DFS is the same idea as backtracking (Lecture 15): advance whenever you can, back up as soon as there is nowhere new to go. Both are most naturally recursive.

DFS, geri izleme (Ders 15) ile aynı fikirdir: ilerleyebildiğiniz sürece ilerleyin, gidilecek yeni bir yer kalmadığı anda geri dönün. Her ikisinin de en doğal biçimi özyinelemelidir.

DFS kenarlara ne yapar?

A DFS gives every edge of an undirected graph a direction: from the vertex that was being explored when the edge was first met. It then falls into one of four classes:

DFS, yönsüz çizgenin her kenarına bir yön verir: kenarla ilk karşılaşıldığında araştırılmakta olan tepeden başlayan yön. Ardından kenar dört sınıftan birine girer:

The reason DFS is so important: in an undirected graph, every edge is either a tree edge or a back edge. Forward edges cannot happen because we would have met the edge from the descendant’s side first, when it was still being explored, which makes it a back edge. Cross edges cannot happen because when we were exploring the earlier vertex we would have discovered the other endpoint through that very edge, making it a tree edge. (In directed graphs all four classes can occur.)

DFS’nin çok önemli olmasının nedeni şudur: yönsüz çizgede her kenar ya ağaç kenarı ya da geri kenardır. İleri kenarlar oluşamaz; çünkü kenarla önce torun tarafından, o hâlâ araştırılırken karşılaşırdık ve bu onu geri kenar yapardı. Çapraz kenarlar da oluşamaz; çünkü önceki tepeyi araştırırken diğer ucu tam bu kenar üzerinden keşfederdik ve bu da onu ağaç kenarı yapardı. (Yönlü çizgelerde dört sınıfın tamamı görülebilir.)

Uygulama: Döngü bulma

Back edges are exactly what cycles look like to DFS. A back edge from x to an ancestor y, together with the tree path from y down to x, forms a cycle. So an undirected graph has a cycle if and only if a DFS meets a back edge:

Geri kenarlar, döngülerin DFS’ye görünen biçimidir. x’ten y atasına giden bir geri kenar, y’den x’e inen ağaç yoluyla birlikte bir döngü oluşturur. Dolayısıyla yönsüz bir çizgede döngü bulunması için ve ancak bunun için DFS’nin bir geri kenarla karşılaşması gerekir:

process_edge(x, y):
    if parent[y] != x:            (not a tree edge, so a back edge)
        print "Cycle from", y, "to", x
        find_path(y, x, parent)
        finished = true

process_edge(x, y):
    if parent[y] != x:      (ağaç kenarı değil, dolayısıyla geri kenar)
        print "Döngü:", y, "→", x
        find_path(y, x, parent)
        finished = true

Uygulama: Eklem tepeleri

An articulation vertex (or cut vertex) of a connected graph is a vertex whose removal disconnects the graph; the phone exchange that, if it failed, would split the network in two. Network designers want to know where these weak points are.

Bağlı bir çizgenin eklem tepesi (veya kesme tepesi), çıkarılması çizgenin bağlantısını koparan tepedir; arızalandığında ağı ikiye bölen bir telefon santrali gibi. Ağ tasarımcıları bu zayıf noktaların nerede olduğunu bilmek ister.

The obvious algorithm deletes each vertex in turn and checks with a DFS whether the rest is still connected: n searches of O(n + m) each, O(n(n + m)).

İlk akla gelen algoritma, her tepeyi sırayla siler ve kalan kısmın hâlâ bağlı olup olmadığını DFS ile denetler: her biri O(n + m) olan n arama, yani O(n(n + m)).

One DFS suffices, O(n + m). In the DFS tree, a non-root vertex v is an articulation vertex exactly when v is not a leaf and some subtree below v has no back edge reaching above v. Such a subtree’s only connection to the rest of the graph runs through v. The slides name the cases: the root is a cut vertex if it has two or more children; a vertex whose child’s subtree sends no back edge up is a bridge cut vertex; a vertex whose subtree’s highest back edge reaches only its parent is a parent cut vertex. Leaves are never articulation vertices.

Tek bir DFS yeterlidir: O(n + m). DFS ağacında kök olmayan bir v tepesi, ancak ve ancak yaprak değilse ve altındaki bir alt ağacın v’nin üstüne ulaşan hiçbir geri kenarı yoksa eklem tepesidir. Böyle bir alt ağacın çizgenin geri kalanıyla tek bağlantısı v üzerinden geçer. Slaytlarda durumlar şöyle adlandırılır: kökün iki veya daha fazla çocuğu varsa kök bir kesme tepesidir; çocuğunun alt ağacı yukarıya hiçbir geri kenar göndermeyen tepe bir köprü kesme tepesidir; alt ağacının en yükseğe çıkan geri kenarı yalnızca ebeveynine ulaşan tepe bir ebeveyn kesme tepesidir. Yapraklar hiçbir zaman eklem tepesi değildir.

Topolojik sıralama

A directed acyclic graph (DAG) has no directed cycles. A topological sort of a DAG is an ordering of its vertices such that every edge points from left to right. The slides’ example DAG orders as G, A, B, C, F, E, D. Every DAG has at least one topological sort, and only DAGs do: a cycle can never be laid out left-to-right.

Yönlü döngüsüz çizge (DAG), yönlü döngü içermez. Bir DAG’nin topolojik sıralaması, her kenar soldan sağa yönelecek biçimde tepelerinin sıralanmasıdır. Slaytlardaki örnek DAG, G, A, B, C, F, E, D biçiminde sıralanır. Her DAG’nin en az bir topolojik sıralaması vardır ve bu özellik yalnızca DAG’lerde bulunur: bir döngü hiçbir zaman soldan sağa yerleştirilemez.

Topological sorting is the tool for scheduling under precedence constraints: which tasks must come before which. Getting dressed is a DAG (socks before shoes, shirt before jacket). Another example from the slides: assembling DNA fragments, where overlaps constrain each fragment to lie left or right of others; build the DAG of constraints, and any topological sort is a consistent assembly, while a cycle proves the data contains errors.

Topolojik sıralama, öncelik kısıtları altında çizelgelemenin aracıdır: hangi işler hangilerinden önce gelmelidir? Giyinmek bir DAG’dir (çoraplar ayakkabılardan, gömlek ceketten önce). Slaytlardan başka bir örnek DNA parçalarının birleştirilmesidir: örtüşmeler, her parçanın diğerlerinin solunda veya sağında bulunmasını gerektirir. Kısıtların DAG’sini kurun; herhangi bir topolojik sıralama tutarlı bir birleştirme verirken bir döngü, veride hata bulunduğunu kanıtlar.

Via DFS. A directed graph is a DAG if and only if a DFS finds no back edges. And listing the vertices in reverse order of finishing (reverse of exit time) gives a topological sort. Why? Consider any edge (x, y) as it is met while exploring x:

DFS ile. Yönlü bir çizge, ancak ve ancak DFS hiçbir geri kenar bulmazsa DAG’dir. Tepeleri tamamlanma sırasının tersinde (çıkış zamanının tersinde) listelemek topolojik sıralamayı verir. Neden? x araştırılırken karşılaşılan herhangi bir (x, y) kenarını düşünün:

If y is undiscovered, we immediately DFS into y, so y finishes before x. Reversing finishing order puts x before y, as required.

y keşfedilmemişse hemen y üzerinde DFS’ye geçeriz; böylece y, x’ten önce tamamlanır. Tamamlanma sırasını ters çevirmek, gerektiği gibi x’i y’den önceye koyar.

If y is discovered but not finished, (x, y) is a back edge, impossible in a DAG.

y keşfedilmiş ama tamamlanmamışsa (x, y) bir geri kenardır; DAG’de bu mümkün değildir.

If y is already finished, it finished before x, so again x precedes y in the reversed order.

y zaten tamamlanmışsa x’ten önce tamamlanmıştır; dolayısıyla ters sırada yine x, y’den önce gelir.

Implementation: push each vertex onto a stack in process_vertex_late, warn if process_edge ever sees a back edge, and pop the stack at the end:

Gerçekleme: process_vertex_late içinde her tepeyi bir yığına ekleyin, process_edge bir geri kenar görürse uyarı verin ve sonunda yığını boşaltın:

topsort(G):
    for each vertex i:
        if not discovered[i]: dfs(G, i)
    pop and print the stack     (reverse finishing order)

topsort(G):
    for her i tepesi:
        if not discovered[i]: dfs(G, i)
    yığından çıkar ve yazdır    (tamamlanma sırasının tersi)

Via repeatedly removing a vertex with no incoming edges. Compute the in-degree (number of incoming edges) of every vertex. Put every vertex with in-degree 0 in a queue. Repeatedly take a vertex from the queue, output it, and decrement the in-degree of everything it points to; any vertex whose in-degree drops to 0 joins the queue. If fewer than n vertices come out, the graph had a cycle. Both methods are O(n + m).

Gelen kenarı olmayan bir tepeyi tekrar tekrar çıkararak. Her tepenin giriş derecesini (gelen kenar sayısını) hesaplayın. Giriş derecesi 0 olan her tepeyi kuyruğa koyun. Kuyruktan sırayla bir tepe alın, çıktıya yazın ve onun işaret ettiği tüm tepelerin giriş derecelerini bir azaltın; giriş derecesi 0’a düşen her tepe kuyruğa katılır. Çıktıda n’den az tepe varsa çizgede döngü vardır. Her iki yöntem de O(n + m)’dir.

Güçlü bağlı bileşenler

A directed graph is strongly connected if there is a directed path between every ordered pair of vertices. Its strongly connected components are the maximal subsets of vertices that are strongly connected among themselves. No vertex can belong to two maximal components, so the components partition the vertices. There is an elegant O(n + m) algorithm based on DFS (closely related to the articulation-vertex algorithm) that finds them; the slides show an example where eight vertices fall into components such as {1, 2, 3, 4, 8} and smaller ones.

Her sıralı tepe çifti arasında yönlü bir yol varsa yönlü çizge güçlü bağlıdır. Güçlü bağlı bileşenleri, kendi içlerinde güçlü bağlı olan maksimal tepe alt kümeleridir. Hiçbir tepe iki maksimal bileşene ait olamaz; dolayısıyla bileşenler tepeleri bölümlere ayırır. Bunları bulan, DFS’ye dayalı (eklem tepesi algoritmasıyla yakından ilişkili) zarif bir O(n + m) algoritması vardır. Slaytlarda sekiz tepenin {1, 2, 3, 4, 8} gibi bir bileşene ve daha küçük bileşenlere ayrıldığı bir örnek gösterilir.

Hazırlık: Birbirinden nefret eden çocukları sıraya dizme

You have n children and m statements “i hates j”. Child i must not stand behind j, or i will throw something.

n çocuk ve “i, j’den nefret ediyor” biçiminde m ifade var. i çocuğu j’nin arkasında durmamalıdır; aksi hâlde i bir şey fırlatacaktır.

One straight line in O(m + n): make a directed graph with an edge i → j for each “i hates j”, meaning i must stand in front of j. A valid line is a topological sort (Lecture 12), and a cycle means no line is possible.

O(m + n) sürede tek bir sıra: Her “i, j’den nefret ediyor” ifadesi için i’nin j’nin önünde durması gerektiğini belirten i → j kenarını içeren yönlü bir çizge kurun. Geçerli sıra bir topolojik sıralamadır (Ders 12); döngü varsa böyle bir sıra mümkün değildir.

Fewest rows, with i in a lower-numbered row than j whenever i hates j: put every child with no incoming edge in row 1, remove them, put the newly source-free children in row 2, and so on. Equivalently, each child’s row number is 1 plus the length of the longest path leading into it, which DFS computes on a DAG in O(m + n). The number of rows is the length of the longest path plus one.

i, j’den nefret ettiğinde i’nin daha küçük numaralı sırada bulunacağı en az sayıda sıra: Gelen kenarı olmayan bütün çocukları 1. sıraya koyup çıkarın; bunun ardından gelen kenarı kalmayanları 2. sıraya koyun ve sürdürün. Eşdeğer olarak, her çocuğun sıra numarası, ona gelen en uzun yolun uzunluğunun 1 fazlasıdır; DFS bunu bir DAG üzerinde O(m + n) sürede hesaplar. Sıra sayısı, en uzun yolun uzunluğunun bir fazlasıdır.

Ağırlıklı çizgeler ve kapsayan ağaçlar

Beyond BFS and DFS lies a whole world of algorithms for graphs whose edges carry weights (lengths, costs, times). The adjacency-list structure from Lecture 10 already has a weight field in each edge node, so nothing changes in the representation.

BFS ve DFS’nin ötesinde, kenarları ağırlık (uzunluk, maliyet, süre) taşıyan çizgeler için geniş bir algoritmalar dünyası vardır. Ders 10’daki komşuluk listesi yapısında her kenar düğümünde zaten bir weight alanı bulunduğundan, gösterimde hiçbir şey değişmez.

A tree is a connected graph with no cycles. A spanning tree of G is a subgraph that contains all the vertices of G and is a tree; it uses exactly n − 1 edges. A minimum spanning tree is a spanning tree whose edge weights add up to the smallest possible total. There may be several (think of a graph where all weights are equal).

Ağaç, döngüsü olmayan bağlı çizgedir. G’nin kapsayan ağacı, G’nin bütün tepelerini içeren ve bir ağaç olan alt çizgedir; tam n − 1 kenar kullanır. Minimum kapsayan ağaç, kenar ağırlıklarının toplamı mümkün olan en küçük değeri veren kapsayan ağaçtır. Birden fazla olabilir (bütün ağırlıkların eşit olduğu bir çizgeyi düşünün).

MSTs are taught because they arise everywhere, because the greedy algorithm provably works, and because clever data structures are needed to make it fast. The first MST algorithm dates from 1926.

MST’ler her yerde ortaya çıktıkları, açgözlü algoritmanın çalıştığı kanıtlanabildiği ve onu hızlandırmak için akıllıca veri yapıları gerektiği için öğretilir. İlk MST algoritması 1926’ya uzanır.

Applications. Building networks: connect a set of sites with the least total wire. Clustering: points joined by an MST fall into natural groups, and deleting the longest MST edges partitions the points into compact clusters (the textbook has a war story about this). The travelling salesman problem: for points in the plane, the optimal tour is at most twice the MST’s length, so walking around the MST gives a decent heuristic tour.

Uygulamalar. Ağ kurma: bir yerleşimler kümesini toplam kablo uzunluğu en az olacak biçimde bağlayın. Kümeleme: MST ile bağlanan noktalar doğal gruplara ayrılır; en uzun MST kenarlarını silmek noktaları sıkı kümelere böler (ders kitabında buna ilişkin bir uygulama öyküsü vardır). Gezgin satıcı problemi: düzlemdeki noktalar için optimal turun uzunluğu, MST uzunluğunun en fazla iki katıdır; dolayısıyla MST’nin çevresinde yürümek makul bir sezgisel tur verir.

Prim algoritması

Start with a single vertex as the tree. Repeatedly add the cheapest edge that connects a tree vertex to a non-tree vertex, together with that vertex. During the run, each vertex is in the tree, on the fringe (one edge from the tree) or unseen.

Ağaç olarak tek bir tepeyle başlayın. Ağaç içindeki bir tepeyi ağaç dışındaki bir tepeye bağlayan en ucuz kenarı, o tepeyle birlikte tekrar tekrar ekleyin. Çalışma sırasında her tepe ya ağacın içinde, ya sınırda (ağaçtan bir kenar uzakta) ya da henüz görülmemiş durumdadır.

Prim(G):
    pick any start vertex s; tree = {s}
    while some vertex is not in the tree:
        pick the minimum-weight edge (x, y) with x in the tree and y not
        add (x, y) and y to the tree

Prim(G):
    herhangi bir s başlangıç tepesi seç; tree = {s}
    while ağaç dışında bir tepe varsa:
        x ağaçta, y ağaç dışında olacak şekilde
            minimum ağırlıklı (x, y) kenarını seç
        (x, y) kenarını ve y’yi ağaca ekle

This always yields a spanning tree, since adding an edge to a new vertex can never close a cycle. But is it a minimum one?

Bu yöntem her zaman kapsayan ağaç üretir; çünkü yeni bir tepeye kenar eklemek asla bir döngüyü kapatamaz. Peki bu ağaç minimum mudur?

Proof that Prim is correct (by contradiction). Suppose Prim fails on some graph. Then there is a first edge (x, y) it adds such that the partial tree can no longer be extended to any MST. Take an actual MST. It does not contain (x, y), but being connected it contains a path from x to y, and that path must at some point leave the partial tree along some edge (v₁, v₂) with exactly one end inside. Swap: remove (v₁, v₂) and add (x, y). The result is still a spanning tree, and since Prim chose (x, y) as the cheapest edge leaving the partial tree, w(x, y) ≤ w(v₁, v₂). If strictly less, the “MST” was not minimum: contradiction. If equal, the new tree is also an MST that contains (x, y), so adding (x, y) was not a fatal mistake after all: contradiction again.

Prim’in doğruluğunun kanıtı (çelişki yoluyla). Prim’in bir çizgede başarısız olduğunu varsayın. O zaman, eklendikten sonra kısmi ağacın artık hiçbir MST’ye genişletilemediği ilk bir (x, y) kenarı vardır. Gerçek bir MST alın. Bu ağaç (x, y)’yi içermez; fakat bağlı olduğu için x’ten y’ye bir yol içerir. Bu yol bir noktada, uçlarından tam biri içeride olan bir (v₁, v₂) kenarı üzerinden kısmi ağacın dışına çıkmalıdır. Değiş tokuş yapın: (v₁, v₂)’yi çıkarın, (x, y)’yi ekleyin. Sonuç hâlâ kapsayan ağaçtır. Prim, (x, y)’yi kısmi ağaçtan çıkan en ucuz kenar olarak seçtiğinden w(x, y) ≤ w(v₁, v₂)’dir. Kesin olarak küçükse “MST” minimum değildir: çelişki. Eşitse yeni ağaç da (x, y)’yi içeren bir MST’dir; dolayısıyla (x, y)’yi eklemek geri dönülmez bir hata değildir: yine çelişki.

Cost. The naive implementation rescans all edges for the cheapest fringe edge each round: n rounds × O(m) = O(nm). The standard implementation keeps, for every non-tree vertex w, distance[w] = the weight of the cheapest edge from the tree to w, and parent[w] = the tree endpoint of that edge:

Maliyet. Naif gerçekleme, her turda en ucuz sınır kenarı için bütün kenarları yeniden tarar: n tur × O(m) = O(nm). Standart gerçekleme, ağaç dışındaki her w tepesi için distance[w] = ağaçtan w’ye giden en ucuz kenarın ağırlığı ve parent[w] = bu kenarın ağaç içindeki ucu bilgilerini tutar:

prim(G, start):
    for every vertex i: intree[i] = false; distance[i] = ∞; parent[i] = −1
    distance[start] = 0; v = start
    while v is not in the tree:
        intree[v] = true              (v joins the tree via edge (parent[v], v))
        for each edge (v, w) with weight wt:
            if not intree[w] and distance[w] > wt:
                distance[w] = wt; parent[w] = v
        v = the non-tree vertex with the smallest distance[]

prim(G, start):
    for her i tepesi:
        intree[i] = false; distance[i] = ∞; parent[i] = −1
    distance[start] = 0; v = start
    while v ağaçta değilse:
        intree[v] = true    (v, (parent[v], v) kenarıyla ağaca katılır)
        for ağırlığı wt olan her (v, w) kenarı:
            if not intree[w] and distance[w] > wt:
                distance[w] = wt; parent[w] = v
        v = distance[] değeri en küçük olan ağaç dışı tepe

Each round costs O(n) to update the neighbours’ distances and O(n) to scan for the minimum, and there are n rounds: O(n²). That is independent of m, which makes Prim ideal for dense graphs (where m is about n² anyway; every edge must be looked at, so O(n²) is optimal there).

Her turda komşuların uzaklıklarını güncellemek O(n), minimumu tarayarak bulmak O(n) sürer ve n tur vardır: O(n²). Bu maliyet m’den bağımsızdır; dolayısıyla Prim yoğun çizgeler için idealdir (buralarda m zaten yaklaşık n²’dir; her kenara bakılmak zorunda olduğundan O(n²) optimaldir).

Kruskal algoritması

On sparse graphs a different greedy order wins. Kruskal considers all the edges from cheapest to most expensive, and adds each one to the growing forest unless it would create a cycle:

Seyrek çizgelerde farklı bir açgözlü sıra üstün gelir. Kruskal bütün kenarları en ucuzdan en pahalıya doğru ele alır ve döngü oluşturmadığı sürece her birini büyüyen ormana ekler:

Kruskal(G):
    sort the edges by weight
    for each edge (x, y) in that order:
        if x and y are in different trees of the forest:
            add (x, y), merging the two trees

Kruskal(G):
    kenarları ağırlıklarına göre sırala
    for bu sıradaki her (x, y) kenarı:
        if x ve y ormanın farklı ağaçlarındaysa:
            iki ağacı birleştirerek (x, y)’yi ekle

The slides run both algorithms on the same 7-vertex graph and, as they must, arrive at the same minimum weight, though the two algorithms add edges in different orders.

Slaytlarda iki algoritma aynı 7 tepeli çizgede çalıştırılır. Kenarları farklı sıralarla ekleseler de, gerektiği gibi aynı minimum ağırlığa ulaşırlar.

Proof that Kruskal is correct. Again suppose there is a first edge (x, y) that Kruskal adds which cannot be extended to an MST. When it was added, x and y were in different trees, so any true MST plus (x, y) contains a cycle through (x, y). Some other edge of that cycle joins the same two pieces, and it was still available when Kruskal chose (x, y); since Kruskal takes edges in increasing order, that edge is at least as heavy. Delete it from the MST and keep (x, y): a spanning tree no heavier than the MST, containing (x, y). Contradiction.

Kruskal’ın doğruluğunun kanıtı. Yine Kruskal’ın eklediği, bir MST’ye genişletilemeyen ilk (x, y) kenarı bulunduğunu varsayın. Eklendiğinde x ve y farklı ağaçlardadır; dolayısıyla herhangi bir gerçek MST’ye (x, y) eklemek, (x, y)’den geçen bir döngü oluşturur. Bu döngünün başka bir kenarı aynı iki parçayı birleştirir ve Kruskal (x, y)’yi seçtiğinde hâlâ kullanılabilir durumdadır. Kruskal kenarları artan sırayla aldığı için bu kenar en az onun kadar ağırdır. Onu MST’den silip (x, y)’yi tutun: MST’den daha ağır olmayan ve (x, y)’yi içeren bir kapsayan ağaç elde edilir. Çelişki.

Cost. Sorting the edges costs O(m log m). The question is how to test “are x and y already connected?” quickly. A BFS through the forest per edge costs O(n), for O(mn) in total. Better: notice that Kruskal is really maintaining connected components, and an edge closes a cycle exactly when both endpoints are already in the same component. So we need a structure supporting two operations:

Maliyet. Kenarları sıralamak O(m log m) sürer. Soru, “x ve y zaten bağlı mı?” sınamasının nasıl hızla yapılacağıdır. Her kenar için ormanda BFS yapmak O(n), toplamda O(mn) maliyetlidir. Daha iyi yaklaşım: Kruskal’ın aslında bağlı bileşenleri tuttuğunu ve bir kenarın ancak iki ucu zaten aynı bileşendeyse döngü kapattığını fark edin. İki işlemi destekleyen bir yapıya ihtiyacımız var:

same_component(v₁, v₂): are these two vertices in the same component?

same_component(v₁, v₂): Bu iki tepe aynı bileşende mi?

merge_components(C₁, C₂): join two components into one.

merge_components(C₁, C₂): İki bileşeni tek bileşende birleştir.

With both in O(log n), Kruskal runs in O(m log m). (Is O(m log n) better than O(m log m)? No: m ≤ n², so log m ≤ 2 log n, and they are the same within a constant.)

Her iki işlem O(log n) olduğunda Kruskal O(m log m) sürede çalışır. (O(m log n), O(m log m)’den daha mı iyidir? Hayır: m ≤ n² olduğundan log m ≤ 2 log n’dir ve sabit çarpan dışında aynıdırlar.)

Birleştir-bul (union-find)

Union-find maintains a collection of disjoint sets with two operations: Find(i) returns a label identifying the set containing i, and Union(i, j) merges the sets containing i and j. Each set is stored as a tree of parent pointers whose root is the set’s label; an array p[i] holds the parent of element i (with p[root] = root), and size[i] holds the number of elements under i.

Union-find, iki işlemle ayrık kümeler topluluğunu tutar: Find(i), i’yi içeren kümeyi tanımlayan etiketi döndürür; Union(i, j), i ve j’yi içeren kümeleri birleştirir. Her küme, kökü kümenin etiketi olan bir ebeveyn işaretçileri ağacı olarak saklanır. p[i] dizisi i elemanının ebeveynini tutar (p[root] = root); size[i] ise i’nin altındaki eleman sayısını tutar.

find(x):
    if p[x] == x: return x
    return find(p[x])                (walk up to the root)

union(a, b):
    r1 = find(a); r2 = find(b)
    if r1 == r2: return              (already in the same set)
    hang the smaller tree under the larger one's root, and add the sizes

find(x):
    if p[x] == x: return x
    return find(p[x])          (köke doğru yukarı yürü)

union(a, b):
    r1 = find(a); r2 = find(b)
    if r1 == r2: return        (zaten aynı kümedeler)
    küçük ağacı büyük ağacın kökünün altına bağla
    ve boyutları topla

Why hang the smaller under the larger? Without that rule the tree can degenerate into a chain: union(1, 2), union(2, 3), … followed by repeated find(1) costs O(n) each. With the rule, a tree’s height only grows when two trees of equal height are merged, so a tree of height h contains at least 2ʰ elements. Hence after any sequence of unions every tree of k nodes has height at most ⌊lg k⌋ (proof by induction on k: merging trees of heights d₁ and d₂ with k₁ ≥ k₂ nodes gives height at most max(d₁, d₂ + 1) ≤ ⌊lg(k₁ + k₂)⌋). So both operations cost O(log n), which is all Kruskal needs.

Küçüğü neden büyüğün altına bağlarız? Bu kural olmadan ağaç bir zincire dönüşebilir: union(1, 2), union(2, 3), … ardından tekrarlanan find(1) çağrılarının her biri O(n) sürer. Kural uygulandığında bir ağacın yüksekliği yalnızca eşit yükseklikte iki ağaç birleştirildiğinde artar; dolayısıyla yüksekliği h olan bir ağaç en az 2ʰ eleman içerir. Böylece herhangi bir birleştirme dizisinden sonra k düğümlü her ağacın yüksekliği en fazla ⌊lg k⌋ olur (k üzerinde tümevarımla kanıt: yükseklikleri d₁ ve d₂, düğüm sayıları k₁ ≥ k₂ olan ağaçların birleştirilmesi en fazla max(d₁, d₂ + 1) ≤ ⌊lg(k₁ + k₂)⌋ yükseklik verir). Dolayısıyla iki işlem de O(log n) maliyetlidir; Kruskal’ın ihtiyacı olan budur.

Path compression. The ideal tree has depth 1, with every element pointing straight at the root. Since a find walks up a path anyway, why not re-point every node on that path directly to the root as we go? With this trick a sequence of n operations costs O(n α(n)), where α is the inverse Ackermann function, a function that grows so slowly that α(number of atoms in the universe) = 5. For every practical purpose union-find with path compression is linear.

Yol sıkıştırma. İdeal ağacın derinliği 1’dir ve her eleman doğrudan kökü gösterir. find zaten bir yol boyunca yukarı yürüdüğüne göre, ilerlerken o yoldaki her düğümü doğrudan köke yönlendirmeyelim mi? Bu teknikle n işlemden oluşan bir dizinin maliyeti O(n α(n)) olur. Buradaki α, ters Ackermann fonksiyonudur; o kadar yavaş büyür ki α(evrendeki atom sayısı) = 5’tir. Pratikte her amaç için, yol sıkıştırmalı union-find doğrusaldır.