Qraf alqoritmlərinin çoxunu artıq bilirsiniz. Real işdə çətin hissə başqadır: məsələni qrafa çevirmək. Bu mövzuda dörd tipik modelə baxırıq: xəritə, sosial şəbəkə, asılılıqlar və şəbəkə (labirint).

Dörd məsələ və onların qraf modelləri
Dörd məsələ və onların qraf modelləri

Dörd sual

  1. Düyünlər nədir? Şəhər, adam, tapşırıq, xana, söz?
  2. Qövslər nədir? Yol, dostluq, "əvvəl gəlir", qonşuluq?
  3. Qövslər yönlüdür? Çəkilidir? (Bax: qrafların təsviri.)
  4. Cavab nədir: ədəd, yol, sıra, yoxsa qruplar?

Sosial şəbəkə

Adamlar düyün, dostluq istiqamətsiz qövsdür. Düyünün dərəcəsi — dostların sayı. BFS "neçə əl sıxma ilə" məsafəni verir (altı əl sıxma qaydası).

python
from collections import deque

friends = {
    "Ali": ["Nigar", "Vusal", "Leyla"],
    "Nigar": ["Ali", "Vusal", "Orxan"],
    "Vusal": ["Ali", "Nigar", "Orxan"],
    "Leyla": ["Ali", "Samir"],
    "Orxan": ["Nigar", "Vusal", "Samir"],
    "Samir": ["Leyla", "Orxan", "Aysel"],
    "Aysel": ["Samir"],
}

def distances(graph, start):
    dist = {start: 0}
    queue = deque([start])
    while queue:
        person = queue.popleft()
        for friend in graph[person]:
            if friend not in dist:
                dist[friend] = dist[person] + 1
                queue.append(friend)
    return dist

print("degrees:", {p: len(f) for p, f in friends.items()})
print("most connected:", max(friends, key=lambda p: len(friends[p])))
print("from Ali:", distances(friends, "Ali"))
text
degrees: {'Ali': 3, 'Nigar': 3, 'Vusal': 3, 'Leyla': 2, 'Orxan': 3, 'Samir': 3, 'Aysel': 1}
most connected: Ali
from Ali: {'Ali': 0, 'Nigar': 1, 'Vusal': 1, 'Leyla': 1, 'Orxan': 2, 'Samir': 2, 'Aysel': 3}

Tövsiyə: dostların dostlarından özümüzü və artıq dostları çıxarıb ortaq dost sayına görə sıralayırıq.

python
from collections import Counter