İçeriğe geç

Graf temelleri

Ders 1 / 16 · 5 dk

Graf temelleri

Adım 1/7

Graf, şeyler ve aralarındaki bağlantılardır. Tanımın tamamı bu.

Fikir

Graf, kenarlarla birbirine bağlanmış düğümlerden (node) oluşur. Tanımın tamamı bu; diziler ve bağlı listeler (linked list) bunun üstüne yalnız kural ekler. Kenarlar yönsüz (iki yönlü bir bağ) ya da yönlü (tek yönlü) olabilir. Bir düğümün derecesi, kaç kenarın ona bağlı olduğudur.

Gerçek hayattan örnek

Molekül, elinde tutabileceğin bir graftır. Atomlar düğüm, kimyasal bağlar kenardır; bütün bağların tekli olduğu durumda bir atomun değerliği onun derecesidir: karbon dört bağ kabul eder, hidrojen yalnızca bir. Kimyagerler formül yerine yapı çizer, çünkü maddenin ne yaptığını atom sayıları değil, bağlantılar belirler.

Kod

Sıra sende

Bu kod ne yazdırır?

g = {"A": ["B", "C"], "B": ["A"], "C": ["A"]}
print(len(g), sum(len(v) for v in g.values()) // 2)

Mini quiz

1 / 3

Her grafın iki bileşeni nedir?