Enine aramanın analizi

Önce enine arama, köşe kümesi $V$‍ ve ayrıt kümesi $E$‍ olan bir grafik için ne kadar zaman alır? Cevap $O(V+E)$‍ zamanıdır.

$O(V+E)$‍ zamanının hangi anlama geldiğini görelim. Şimdilik $|E|\ge |V|$‍ varsayalım; bu, çoğu grafik için geçerlidir, özellikle de önce enine arama yaptığımız grafikler için. O zaman $|V|+|E|\le |E|+|E|=2\cdot |E|$‍. Asimptotik gösterimde sabit çarpanları göz ardı ettiğimiz için, $|E|\ge |V|$‍ olduğunda, $O(V+E)$‍'nin aslında $O(E)$‍ olduğunu görürüz. Eğer, bununla birlikte, $|E|<|V|$‍ ise, bu durumda $|V|+|E|\le |V|+|V|=2\cdot |V|$‍ ve buna göre, $O(V+E)$‍ gerçekten $O(V)$‍ anlamına gelir. $O(V+E)$‍'nin gerçek anlamının $O(max(V,E))$‍ olduğunu söyleyerek iki durumu birleştirebiliriz. Genelde, $x$‍ ve $y$‍ parametreleri varsa, $O(x+y)$‍'nin gerçek anlamı, $O(max(x,y))$‍ olur.

(Bu arada, her köşeden diğer köşelere bir yol varsa, bir grafiğin bağlantılı olduğuna dikkat edin. Bir grafiğin bağlantılı olmak koşuluyla sahip olabileceği minimum kenar sayısı $|V|-1$‍'dir. $|E|=|V|-1$‍ olan bir grafiğe serbest ağaç deriz.)

Enine arama nasıl oluyor da, $O(V+E)$‍ zamanında çalışıyor? Her bir köşe için uzaklık ve öncülü başlatmak $O(V)$‍ zaman alıyor (aslında, $\mathrm{\Theta }(V)$‍ zaman). Her bir köşeye en fazla bir kere gidilir, çünkü sadece ilk ulaşılan zamanda uzaklık null olur ve böylece her köşe en fazla bir kere sıralanır. Bir köşeye gelen ayrıtları sadece onlara geldiğimizde incelediğimiz için, her bir ayrıt en fazla iki kere, gelen her bir ayrıt için bir kere incelenir. Böylece, önce enine arama köşelere gitmek için $O(V+E)$‍ zaman harcar.

Bu içerik Dartmouth Bilgisayar Bilimleri öğretim görevlileri Thomas Cormen ve Devin Balkcom ile Khan Academy bilgisayar bölümü içeriklerini hazırlayan takımın işbirliği ile hazırlanmıştır. İçerik CC-BY-NC-SA lisanslıdır.