Graf (Graph)

#Nasıl çalışır?

Graf (graph), düğümlerden (vertex) ve onları birbirine bağlayan kenarlardan (edge) oluşur. Yol haritaları, sosyal ağlar, bilgisayar ağları ve web sayfaları arasındaki bağlantılar graflarla modellenir.

Kenarlar yönlü (tek yönlü yol, takip etme) ya da yönsüz (iki yönlü yol, arkadaşlık) olabilir; ağırlık da taşıyabilir (mesafe, maliyet). Bu derste yönsüz ve ağırlıksız bir graf kullanıyoruz.

Graf genellikle komşuluk listesiyle saklanır: her düğüm için komşularının listesi tutulur. Alternatifi komşuluk matrisidir: n×n bir tabloda i ile j arasında kenar varsa 1 yazılır. Gezinmenin iki temel yolu genişlik öncelikli (BFS) ve derinlik öncelikli (DFS) aramadır.

#Kendin dene

#Temel işlemler

BFS(start)

Başlangıçtan katman katman yayılır: önce tüm komşular, sonra onların komşuları. Bir kuyruk kullanır. Ağırlıksız grafta en kısa yolu (en az kenarı) bulur.

DFS(start)

Bir yol boyunca gidebildiği kadar derine iner, çıkmaza girince geri döner (backtrack). Özyineleme ya da yığın kullanır. Döngü bulma, bağlı bileşenler ve topolojik sıralama için temeldir.

addEdge(u, v)

Yönsüz grafta v'yi u'nun, u'yu v'nin komşuluk listesine ekler.

removeEdge(u, v)

Kenarı iki komşuluk listesinden de çıkarır.

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

from collections import deque

# Adjacency list: graph[u] holds u's neighbours.
graph: dict[int, list[int]] = {node: [] for node in range(1, 8)}
for u, v in [(1, 2), (1, 3), (2, 4), (2, 5), (3, 5), (3, 6), (4, 7), (5, 7), (6, 7)]:
    graph[u].append(v)  # undirected: add both directions
    graph[v].append(u)


def bfs(start: int) -> list[int]:
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in graph[u]:
            if v not in visited:  # mark when queued so each node is queued once
                visited.add(v)
                queue.append(v)
    return order


def dfs(u: int, visited: set[int], order: list[int]) -> list[int]:
    visited.add(u)
    order.append(u)
    for v in graph[u]:
        if v not in visited:
            dfs(v, visited, order)
    return order


print(*bfs(1))  # layer by layer
print(*dfs(1, set(), []))  # as deep as possible, then backtrack

#Karmaşıklık

V düğüm, E kenar sayısıdır. BFS ve DFS her düğümü bir kez ziyaret eder ve her kenara (yönsüz grafta iki uçtan) bakar: O(V + E). Komşuluk listesi seyrek graflarda (kenar sayısı az) çok daha az bellek kullanır; matris ise yoğun graflarda ve kenar sorgusunun çok sık olduğu durumlarda tercih edilir.

#Ne zaman kullanılır?

Navigasyonda en kısa rota (Dijkstra, A*), sosyal ağlarda "tanıyor olabileceğin kişiler" (BFS ile 2. derece komşular), web tarayıcılarının sayfaları gezmesi, derleyicilerde bağımlılık sırası (topolojik sıralama), labirent çözme ve ağlarda bağlantı analizi graf algoritmalarıyla yapılır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Genişlik Öncelikli Arama (BFS)
• Derinlik Öncelikli Arama (DFS)
• Ayrık Kümeler (Union-Find)