You already know most graph algorithms. In real work the hard part is different: turning a task into a graph. This topic covers four typical models: a map, a social network, dependencies and a grid (a maze).

Four tasks and their graph models
Four tasks and their graph models

Four questions

  1. What are the vertices? A city, a person, a task, a cell, a word?
  2. What are the edges? A road, a friendship, "comes before", adjacency?
  3. Are the edges directed? Weighted? (See graph representations.)
  4. What is the answer: a number, a path, an order or groups?

A social network

People are vertices and friendship is an undirected edge. The degree of a vertex is its number of friends. BFS gives the distance in "handshakes" (the six degrees of separation).

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}

Suggestions: take friends of friends, drop ourselves and existing friends, and rank by the number of mutual friends.

python
from collections import Counter