Большинство алгоритмов на графах вам уже знакомо. В реальной работе трудно другое: превратить задачу в граф. В этой теме разберём четыре типичные модели: карта, соцсеть, зависимости и сетка (лабиринт).

Четыре задачи и их модели в виде графа
Четыре задачи и их модели в виде графа

Четыре вопроса

  1. Что такое вершины? Город, человек, задача, клетка, слово?
  2. Что такое рёбра? Дорога, дружба, «раньше», соседство?
  3. Рёбра ориентированные? Взвешенные? (См. представление графов.)
  4. Что нужно в ответе: число, путь, порядок или группы?

Социальная сеть

Люди — вершины, дружба — неориентированное ребро. Степень вершины — число друзей. BFS даёт расстояние «через сколько рукопожатий» (правило шести рукопожатий).

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}

Рекомендации: берём друзей друзей, исключаем себя и уже друзей, сортируем по числу общих друзей.

python
from collections import Counter