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.
Yapabilmene rağmen JavaScript'te veri yapıları oluşturun ve diğer dillerde, bir grafiği çeşitli şekillerde uygulayabilirsiniz. En popüler yaklaşımlar kenar listeleri, komşuluk listeleri, ve komşuluk matrisleri.
bu Grafikleri temsil etmek için Khan Academy 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. arasında ortak bir ayrım vardır.
yönlendirilmiş ve yönsüz grafikler; 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 bir grafik, aynı zamanda olarak da adlandırılır digraf.
- Yönsüz grafik: Yönsüz graf, iki yönlü graf olarak da bilinir. Yönsüz grafiklerde kenarların yönü önemli değildir ve geçiş herhangi bir yöne gidebilir.
- 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.
- Sonlu grafik: Sınırlı sayıda düğümü ve kenarı olan bir grafik.
- Sonsuz grafik: Sonsuz sayıda düğümü ve kenarı olan bir grafik.
- Önemsiz grafik: Sadece bir düğümü olan ve kenarı olmayan bir grafik.
- Basit grafik: Bir grafiğin düğümlerinin her bir çiftini yalnızca bir kenar birbirine bağladığında, buna basit grafik denir.
- Boş grafik: Boş bir grafik, düğümlerini birbirine bağlayan kenarları olmayan bir grafiktir.
- Ç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.
- Komple grafik: Tam bir grafik, her düğümün grafikteki diğer tüm düğümlere bağlandığı bir grafiktir. olarak da bilinir. tam grafik.
- Sözde grafik: Diğer grafik kenarlarından ayrı olarak kendi kendine döngüsü olan bir grafa sözde graf denir.
- Normal grafik: Normal 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.
- 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ğlantısı kesilmiş grafik: Bağlantısı kesilmiş bir grafik, bağlantılı bir grafiğin tam tersidir. Bağlantısı kesilmiş bir grafikte, grafiğin düğümlerini birbirine bağlayan kenarlar yoktur; hükümsüz 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.
- Asiklik grafiği: Asiklik bir grafik, hiç çevrimi olmayan bir grafiktir. Yönlendirilmiş veya yönlendirilmemiş olabilir.
- alt yazı: Bir alt grafik, türetilmiş bir grafiktir. Başka bir grafiğin alt kümeleri olan düğümlerden ve kenarlardan oluşan bir grafiktir.
A döngü bir grafikte bir düğümden başlayan ve aynı düğümde biten bir kenardır. Bu nedenle, bir kendi kendine döngü sözde grafikte görüldüğü gibi, yalnızca bir grafik düğümü üzerinde 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 öncelikli 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. Seçilen herhangi bir düğümden bir grafiği çaprazlamaya 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 alt düğümlerini veya dallarını araştırır; yani, geniş gitmeden ö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 eyaletlerini bir grafik gibi düşünün ve iki eyalet olup olmadığını kontrol etmeye çalışın, X ve Y, bağlılar. Derinlik öncelikli bir arama, yeterince erken farkına varmadan neredeyse ülkenin her yerine gidebilir. Y sadece 2 eyalet uzakta X.
Genişlik öncelikli aramanın avantajı, bir sonrakine geçmeden önce mevcut düğüme mümkün olduğunca yakınlığı korumasıdır. arasındaki bağlantıyı bulacaktır. X ve Y tüm ülkeyi keşfetmek zorunda kalmadan kısa sürede.
Bu iki algoritma arasındaki bir diğer önemli fark, kodda uygulanma biçimleridir. Genişlik öncelikli arama, yinelemeli algoritma ve bir kullanır sıra, derinlik öncelikli arama genellikle bir özyinelemeli algoritma bundan yararlanan yığın.
Aşağıda, her iki algoritmanın uygulanmasını gösteren bazı sözde kodlar bulunmaktadır.
Genişlik-İlk Arama
bfs (Grafik G, GraphNode kökü) {
İzin Vermek q olmak yeni Sıra// kökü ziyaret edildi olarak işaretle
root.ziyaret edilen = doğru// kuyruğa kök ekle
q.sıraya almak(kök)
süre (q değil boş) {
İzin Vermek geçerli olmak q.dequeue() // kuyruktaki ön elemanı kaldır
for (G'deki akımın komşuları n) {
eğer (n dır-dirolumsuzluk henüz ziyaret edildi) {
// sıraya ekle - böylece komşularını da keşfedebilirsin
q.sıraya almak(n)
n.ziyaret edilen = doğru
}
}
}
}
Derinlik öncelikli arama
dfs (Grafik G, GraphNode kökü) {
// temel durum
eğer (kök hükümsüz) dönüş// kökü ziyaret edildi olarak işaretle
root.ziyaret edilen = doğru
for (G'deki kök n komşuları)
eğer (n dır-dirolumsuzluk henüz ziyaret edildi)
dfs (G, n) // özyinelemeli çağrı
}
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: Bu kullanılır yönlendirilmiş grafikler düğümleri istenen sırada sıralamak için. 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. Aynı zamanda iki düğüm arasındaki en kısa yolu bulmak için de kullanılır. ağırlıklı yönlendirilmiş grafik, döngüleri olabilir veya olmayabilir.
Grafiklere Dayalı Ortak Mülakat Soruları
Grafikler önemli her programcının bilmesi gereken veri yapıları. 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ı deneyebilirsin LeetKodu, HackerRütbesi, veya GeeksforGeeks.
Grafik Veri Yapılarını ve Algoritmaları Anlama
Grafikler sadece teknik görüşmeler için kullanışlı değildir. Gerçek dünyadaki kullanım durumları da var, örneğin ağ, haritalar, ve havayolu sistemleri yolları bulmak için. 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.
