Graf modeli ve adjacency temsilleri

Graf G=(V,E), nesneleri ve aralarındaki ilişkileri tanımlar. Yönlü/yönsüz, ağırlıklı/ağırlıksız, multigraph, self-loop ve bağlantısız bileşenler sözleşmede belirtilmelidir. Yönsüz edge listesinde bir ilişki, adjacency listesinde çoğunlukla iki komşuluk kaydıdır; E sayımını karıştırma.

Adjacency matrix V² hücre kullanır ve edge lookup O(1)'dir; komşu tarama O(V). Adjacency list O(V+E) alan ve degree kadar komşu taraması sağlar; düz listede belirli edge lookup O(degree). Edge list Kruskal gibi bütün kenarları sıralayan algoritmalara uygundur. Çok büyük graflarda CSR sıkıştırılmış ardışık komşulukla locality iyileştirir.

Düğüm etiketi ile array indeksi farklı olabilir. Önce etiketleri dense ID'lere eşle veya dictionary kullan. Grafı immutable snapshot mı canlı güncellenen yapı mı kabul ediyorsun? Traversal sırasında değişen adjacency iteration davranışını bozabilir. Her algoritmada yalnız root'tan erişilen düğümler ile bütün V'nin işlenmesini ayır.

def undirected_graph(vertices, edges):
    g = {v: [] for v in vertices}
    for a, b in edges:
        g[a].append(b); g[b].append(a)
    return g
assert undirected_graph("ABC", [("A","B"),("B","C")])["B"] == ["A","C"]