Çizge
- İngilizcesi
- Graph
- Türkçe karşılığı
- graf
- Okunuşu
- gref
Günlük kullanımda iki ad da yaygın.
Kısaca
Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan ve yollar, arkadaşlıklar ve bağımlılıklar gibi ilişkileri modellemekte kullanılan bir veri yapısıdır.
Çizge (graph) veri yapısı nedir?
Çizge, düğümlerden (köşe, vertex de denir) ve düğüm çiftlerini birbirine bağlayan kenarlardan oluşan bir kümedir. Ağaçtan farklı olarak çizgenin kökü ve ebeveyn-çocuk kuralı yoktur: herhangi bir düğüm başka herhangi birine bağlanabilir ve kenarlar döngüler oluşturabilir. Çizgeler yönlü olabilir; burada her kenar tek yönlü bir sokak gibi bir yöne işaret eder. Ya da yönsüz olabilir; burada kenarlar iki yönde de çalışır. Ayrıca ağırlıklı da olabilirler; yani her kenar mesafe, maliyet ya da süre gibi bir değer taşır.
Programlar bir çizgeyi genellikle komşuluk listesi (adjacency list) olarak saklar; bu liste her düğümü komşularının listesine eşler ve O(V + E) bellek kullanır (V köşe sayısı, E kenar sayısı). Alternatif, iki düğümün bağlı olup olmadığını O(1)'de kontrol eden ama her zaman O(V^2) bellek kullanan V x V boyutunda bir ızgara olan komşuluk matrisidir. Genişlik öncelikli arama (BFS) ve derinlik öncelikli arama (DFS), komşuluk listesiyle ulaşılabilen her düğümü O(V + E) sürede ziyaret eder; BFS en az kenarlı yolu bulurken Dijkstra algoritması kenar ağırlıkları negatif olmadığında en ucuz yolu bulur.
Bir metro haritası iyi bir zihinsel modeldir: istasyonlar düğümler, aralarındaki raylar kenarlardır. Çizgeler sosyal ağları (insanlar ve arkadaşlıklar), navigasyonu (kavşaklar ve yollar), web'i (sayfalar ve bağlantılar), bilgisayar ağlarını ve nelerin kurulacağına karar vermek için bağımlılık çizgesi oluşturan paket yöneticilerini modeller. Derleme araçları ve görev zamanlayıcılar, görevlerin her biri bağımlı olduğu her şeyden sonra çalışacak şekilde sıralanabilmesi için döngüsüz yönlü çizgeye (DAG) yani döngüsü olmayan yönlü bir çizgeye dayanır.
Bilgisayar biliminde çizge, bir grafik ya da verinin çizimi değildir; bağlantıların bir modelidir. Ağaç, bağlantılı ve döngüsüz olan çizgenin özel bir halidir. Genel çizgeler döngü içerebildiği için gezinme kodu hangi düğümleri zaten ziyaret ettiğini takip etmelidir; aksi halde sonsuza kadar döngüde kalabilir.
Önemli noktalar
- Çizge, kenarlarla bağlı düğümlerden (köşelerden) oluşan bir kümedir.
- Kenarlar yönlü ya da yönsüz, ağırlıklı ya da ağırlıksız olabilir.
- Komşuluk listesi O(V + E) bellek kullanır ve görece az kenarlı seyrek çizgeler için olağan seçimdir.
- BFS ve DFS ulaşılabilen her düğümü O(V + E) sürede ziyaret eder.
- Çizgeler döngü içerebildiği için gezinmeler ziyaret edilen düğümleri izlemelidir.
Örnek
# A directed graph as an adjacency list: package -> packages it depends on
graph = {"app": ["auth", "db"], "auth": ["db", "crypto"], "db": [], "crypto": []}
def dfs(node, seen):
# Depth-first search: follow each edge, skipping nodes already visited
seen.add(node)
for neighbor in graph[node]:
if neighbor not in seen:
dfs(neighbor, seen)
return seen
print(sorted(dfs("app", set()))) # ['app', 'auth', 'crypto', 'db']Sık sorulan sorular
Çizge ile ağaç arasındaki fark nedir?
Ağaç, ek kuralları olan bir çizgedir: bağlantılıdır, döngü içermez ve genellikle tek bir kökü vardır. Çizge ise döngülere, birkaç kopuk parçaya ve herhangi bir bağlantı örüntüsüne sahip olabilir.
Döngüsüz yönlü çizge (DAG) nedir?
DAG, döngüsü olmayan yönlü bir çizgedir; yani kenarları izlemek sizi asla başladığınız yere geri götüremez. DAG'lar derleme adımları, veri pipeline'ları ve Git'teki commit geçmişi gibi bağımlılıkları modeller.
Ne zaman DFS yerine BFS kullanmalıyım?
Başlangıçtan uzaklık sırasına göre düğümleri keşfettiği için kenar sayısına göre en kısa yola ihtiyaç duyduğunuzda genişlik öncelikli aramayı kullanın. Tüm yolları keşfetmek, döngüleri bulmak ya da bağımlılıkları sıralamak için derinlik öncelikli aramayı kullanın; ikisi de O(V + E) sürede çalışır.
İlgili sayfalar
- AğaçVeri Yapıları, s. 2Ağaç, kenarlarla bağlı düğümlerden oluşan hiyerarşik bir veri yapısıdır; en üstte tek bir kök düğüm ve altında dallanan çocuk düğümler bulunur.
- KuyrukVeri Yapıları, s. 24Kuyruk, öğeleri ilk giren ilk çıkar (FIFO) sırasıyla saklayan bir veri yapısıdır; en uzun süre bekleyen öğe her zaman çıkarılacak sonraki öğedir.
- YığınVeri Yapıları, s. 36Yığın, öğeleri son giren ilk çıkar (LIFO) sırasıyla saklayan bir veri yapısıdır; en son eklenen öğe her zaman ilk çıkarılan öğedir.
- ÖzyinelemeProgramlamanın Temelleri, s. 42Özyineleme, bir fonksiyonun sorunu, basit bir temel duruma ulaşana dek aynı sorunun daha küçük sürümleri için kendisini çağırarak çözdüğü tekniktir.
- AlgoritmaProgramlamanın Temelleri, s. 1Algoritma, bir listeyi sıralamak ya da en kısa yolu bulmak gibi bir sorunu çözmek veya bir işi tamamlamak için izlenen, sonlu ve adım adım yönergeler bütünüdür.
- Big O gösterimiProgramlamanın Temelleri, s. 4Big O gösterimi, girdi büyüdükçe bir algoritmanın çalışma süresinin ya da bellek kullanımının nasıl arttığını, kesin hız yerine büyüme oranıyla anlatır.
- Union-FindVeri Yapıları, s. 35Union-find (ayrık küme birleşimi), öğe gruplarını izleyip birleştiren ve iki öğenin bağlı olup olmadığını neredeyse anında söyleyen veri yapısıdır.
- Çizge VeritabanıVeritabanları, s. 5Çizge veritabanı, veriyi ilişkilerle bağlı düğümler olarak saklar; arkadaşların arkadaşları ya da öğe bağımlılıkları gibi bağlantıları izlemeyi hızlandırır.
- Topolojik SıralamaVeri Yapıları, s. 32Topolojik sıralama, döngüsüz yönlü bir çizgenin düğümlerini, A'dan B'ye her kenar için listede A'nın B'den önce geleceği biçimde sıralayan algoritmadır.
Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin