Etkili bir programcı, veri yapıları ve algoritmalar hakkında sağlam bir anlayışa ihtiyaç duyar. Teknik görüşmeler genellikle problem çözme ve eleştirel düşünme becerilerinizi test eder.

Grafikler, programlamadaki birçok önemli veri yapısından biridir. Çoğu durumda, grafikleri anlamak ve grafik tabanlı sorunları çözmek kolay olmuyor.

Grafik nedir ve onun hakkında bilmeniz gerekenler nelerdir?

Grafik Nedir?

Grafik, düğümleri (veya köşeleri) ve bunları birbirine bağlayan kenarları olan doğrusal olmayan bir veri yapısıdır. Tüm ağaçlar grafiklerin alt türleridir, ancak tüm grafikler ağaç değildir ve grafik, ağaçların kaynaklandığı veri yapısıdır.

Bir grafiğin görsel temsili

JavaScript ve diğer dillerde veri yapıları oluşturabilmenize rağmen , bir grafiği çeşitli şekillerde uygulayabilirsiniz. En popüler yaklaşımlar, kenar listeleri , bitişiklik listeleri ve bitişiklik matrisleridir .

Khan Academy grafikleri temsil etme kılavuzu, bir grafiğin nasıl temsil edileceğini öğrenmek için harika bir kaynaktır.

Birçok farklı grafik türü vardır. Ortak bir ayrım, yönlendirilmiş ve yönlendirilmemiş grafikler arasındadır; bunlar kodlama zorlukları ve gerçek hayattaki kullanımlarda çokça karşımıza çıkıyor.

Grafik Türleri

Yönlendirilmiş grafik: Tüm kenarların bir yönü olduğu, digraf olarak da adlandırılan bir grafik.

Yönlendirilmiş bir grafik

Yönsüz çizge : Yönsüz çizge, iki yönlü çizge olarak da bilinir. Yönsüz grafiklerde kenarların yönü önemli değildir ve geçiş herhangi bir yöne gidebilir.

Yönsüz bir grafik

Ağırlıklı grafik: Ağırlıklı grafik , düğümleri ve kenarları ilişkili bir değere sahip bir grafiktir. Çoğu durumda, bu değer, o düğümü veya kenarı keşfetme maliyetini temsil eder.

ağırlıklı grafik

Sonlu grafik: Sınırlı sayıda düğümü ve kenarı olan bir grafik.

Sonlu bir grafik

Sonsuz grafik: Sonsuz miktarda düğüm ve kenara sahip bir grafik.

Sonsuz bir grafik

Önemsiz grafik: Sadece bir düğümü olan ve kenarı olmayan bir grafik.

Önemsiz bir grafik

Basit grafik: Bir grafiğin her bir düğüm çiftini yalnızca bir kenar birbirine bağladığında, buna basit grafik denir.

Basit bir grafik

Boş grafik: Boş grafik, düğümlerini birbirine bağlayan kenarları olmayan bir grafiktir.

Boş bir grafik

Çoklu Grafik: Bir çoklu grafikte, en az bir çift düğüm, onları birbirine bağlayan birden fazla kenara sahiptir. Çoklu grafiklerde kendi kendine döngüler yoktur.

Çoklu grafik

Tam grafik: Tam bir grafik, her düğümün grafikteki diğer tüm düğümlere bağlandığı bir grafiktir. Tam grafik olarak da bilinir .

Tam bir grafik

Sözde grafik: Diğer grafik kenarlarından ayrı olarak kendi kendine döngüsü olan bir grafa sözde grafik denir.

Sahte bir grafik

Düzenli grafik: Düzenli bir grafik, tüm düğümlerin eşit derecelere sahip olduğu bir grafiktir; yani her düğümün aynı sayıda komşusu vardır.

Normal bir grafik

Bağlı grafik: Bağlı bir grafik, herhangi iki düğümün bağlandığı herhangi bir grafiktir; yani, grafiğin her iki düğümü arasında en az bir yol bulunan bir grafik.

Bağlı bir grafik

Bağlantısı kesilmiş grafik: Bağlantısı kesilmiş bir grafik, bağlantılı bir grafiğin tam tersidir. Bağlantısı kesilmiş bir grafikte, örneğin boş bir grafikte olduğu gibi, grafiğin düğümlerini birbirine bağlayan kenarlar yoktur .

Bağlantısı kesilmiş bir grafik

Döngüsel grafik: Döngüsel grafik, en az bir grafik döngüsü (başladığı yerde biten bir yol) içeren bir grafiktir.

Döngüsel bir grafik

Döngüsel olmayan grafik: Döngüsel olmayan bir grafik, hiç döngüsü olmayan bir grafiktir. Yönlendirilmiş veya yönlendirilmemiş olabilir.

asiklik bir grafik

Alt Grafik : Bir alt grafik, türetilmiş bir grafiktir. Başka bir grafiğin alt kümeleri olan düğümlerden ve kenarlardan oluşan bir grafiktir.

bir alt yazı

Bir grafikteki döngü , bir düğümden başlayan ve aynı düğümde biten bir kenardır. Bu nedenle, bir kendi kendine döngü , sözde bir grafikte görüldüğü gibi, yalnızca bir grafik düğümü üzerindeki bir döngüdür.

Grafik Geçiş Algoritmaları

Doğrusal olmayan bir veri yapısı türü olduğundan, bir grafiğin üzerinden geçmek oldukça zordur. Bir grafiğin üzerinden geçmek, kenarlardan geçen geçerli bir yol olduğu göz önüne alındığında, her bir düğümün içinden geçmek ve keşfetmek anlamına gelir. Grafik geçiş algoritmaları temel olarak iki tiptedir.

Genişlik-İlk Arama (BFS): Genişlik-ilk arama, bir grafik düğümünü ziyaret eden ve alt düğümlerinden herhangi birine gitmeden önce komşularını araştıran bir grafik geçiş algoritmasıdır. Grafiği seçilen herhangi bir düğümden geçmeye başlayabilmenize rağmen, kök düğüm genellikle tercih edilen başlangıç ​​noktasıdır.

Derinlik-İlk Arama (DFS): Bu, ikinci ana grafik geçiş algoritmasıdır. Bir grafik düğümünü ziyaret eder ve bir sonraki düğüme geçmeden önce onun alt düğümlerini veya dallarını araştırır; yani, genişlemeden önce önce derine iner.

Genişlik öncelikli arama, iki düğüm arasındaki yolları, özellikle de en kısa yolu olabildiğince çabuk bulmak için önerilen algoritmadır.

Derinlik öncelikli arama, çoğunlukla grafikteki her düğümü ziyaret etmek istediğinizde önerilir. Her iki geçiş algoritması da her durumda iyi çalışır, ancak seçilen senaryolarda biri diğerinden daha basit ve daha optimize olabilir.

Basit bir örnek, her iki algoritmayı da daha iyi anlamanıza yardımcı olabilir. Bir ülkenin durumlarını bir grafik olarak düşünün ve X ve Y olmak üzere iki devletin birbirine bağlı olup olmadığını kontrol etmeye çalışın. Derinlik öncelikli bir arama, Y’nin X’ten yalnızca 2 eyalet uzakta olduğunu yeterince erken fark etmeden neredeyse ülke çapında bir yola gidebilir .

Genişlik öncelikli aramanın avantajı, bir sonrakine geçmeden önce mevcut düğüme mümkün olduğunca yakınlığı korumasıdır. Tüm ülkeyi keşfetmeye gerek kalmadan X ve Y arasındaki bağlantıyı kısa sürede bulacaktır .

Bu iki algoritma arasındaki bir diğer önemli fark, kodda uygulanma biçimleridir. Genişlik öncelikli arama yinelemeli bir algoritmadır ve bir kuyruktan yararlanırken , derinlik öncelikli arama genellikle yığından yararlanan özyinelemeli bir algoritma olarak uygulanır .

Aşağıda, her iki algoritmanın uygulanmasını gösteren bazı sözde kodlar bulunmaktadır.

Genişlik-İlk Arama

bfs(Graph G, GraphNode root) {

    let q be new Queue

    // mark root as visited

    root.visited = true

    // add root to the queue

    q.enqueue(root)

    while (q is not empty) {

        let current be q.dequeue() // remove front element in the queue

        for(neighbors n of current in G) {

            if (n is not yet visited) {

                // add to the queue – so you can explore its neighbors too

                q.enqueue(n)

                n.visited = true

            }

        }

    }

}

Derinlik öncelikli arama

dfs(Graph G, GraphNode root) {

    // base case

    if (root is null) return

    // mark root as visited

    root.visited = true

    for (neighbors n of root in G)

        if (n is not yet visited)

            dfs(G, n) // recursive call

}

Diğer birkaç grafik çapraz geçiş algoritması, genişlik öncelikli ve derinlik öncelikli aramalardan türetilir. En popüler olanlar:

• Çift yönlü arama: Bu algoritma, iki düğüm arasındaki en kısa yolu bulmanın optimize edilmiş bir yoludur. Bir yol varsa çarpışan iki genişlik öncelikli arama kullanır.
• Topolojik sıralama: Yönlendirilmiş grafiklerde düğümleri istenen sırada sıralamak için kullanılır . Yönsüz grafiklere veya döngülü grafiklere topolojik sıralama uygulayamazsınız.
• Dijkstra’nın algoritması: Bu aynı zamanda bir BFS türüdür. Ayrıca, döngüleri olan veya olmayan ağırlıklı yönlendirilmiş bir grafikte iki düğüm arasındaki en kısa yolu bulmak için kullanılır .

Grafiklere Dayalı Ortak Mülakat Soruları

Grafikler, her programcının bilmesi gereken önemli veri yapıları arasındadır . Teknik mülakatlarda genellikle bu konu ile ilgili sorular gelir ve konuyla ilgili bazı klasik problemlerle karşılaşabilirsiniz. Bunlara “kasaba hakimi”, “adaların sayısı” ve “gezgin satıcı” sorunları gibi şeyler dahildir.

Bunlar, birçok popüler grafik tabanlı görüşme probleminden sadece birkaçıdır. Bunları LeetCode , HackerRank veya GeeksforGeeks üzerinde deneyebilirsiniz .

Grafik Veri Yapılarını ve Algoritmaları Anlama

Grafikler sadece teknik görüşmeler için kullanışlı değildir. Rota bulmak için ağ oluşturma, haritalar ve havayolu sistemleri gibi gerçek dünya kullanım durumları da vardır . Ayrıca bilgisayar sistemlerinin temel mantığında da kullanılırlar.

Grafikler, verileri düzenlemek ve karmaşık sorunları görselleştirmemize yardımcı olmak için mükemmeldir. Grafikler, alan karmaşıklığını veya bellek sorunlarını önlemek için yalnızca kesinlikle gerekli olduğunda kullanılmalıdır.