Qraf G = (V, E) təpələr çoxluğu V və onları birləşdirən tillər çoxluğu E-dir. Şəhərlər və yollar, insanlar və dostluqlar, fayllar və asılılıqlar: hamısı qrafdır. Onunla kodda işləmək üçün əvvəlcə necə saxlayacağımızı seçməliyik.

5 təpəli bir qraf matris, qonşuluq siyahıları və tillər siyahısı kimi
5 təpəli bir qraf matris, qonşuluq siyahıları və tillər siyahısı kimi

Terminlər

  • yönlü qraf: u -> v tili yalnız bir istiqamətdədir; yönsüz: hər iki istiqamətdə;
  • çəkili qraf: hər tilin ədədi var (məsafə, qiymət);
  • təpənin dərəcəsi onun tillərinin sayıdır; yönlü qrafda daxil olan və çıxan dərəcə ayrıca sayılır;
  • yol tillərlə bağlı təpələr ardıcıllığıdır, dövr başlanğıca qayıdan yoldur, istənilən iki təpə arasında yol varsa qraf bağlıdır;
  • E təxminən V qədərdirsə qraf seyrək, təxminən V² qədərdirsə sıxdır.

Üç təsvir

Qonşuluq matrisi n x n cədvəldir: u -> v tili varsa matrix[u][v] = 1. Qonşuluq siyahısı hər təpə üçün qonşuların siyahısını saxlayır. Tillər siyahısı sadəcə (u, v) cütlərinin siyahısıdır.

python
n = 5
edges = [(0, 1), (0, 2), (1, 2), (1, 3), (3, 4)]