Графы. Пример на PHP

Графы являются важными структурами данных, используемыми в программировании для представления иерархий и связей.

Граф состоит из узлов (вершин) и рёбер, соединяющих эти узлы. Графы бывают направленными (где каждое ребро имеет направление) и ненаправленными.

Представление графа

class Graph {
    public $graph;
    public function __construct() {
        $this->graph = [];
    }

    public function addEdge($start, $end) {
        $this->graph[$start][] = $end;
        // Для ненаправленного графа добавьте также обратное ребро:
        // $this->graph[$end][] = $start;
    }

    public function getGraph() {
        return $this->graph;
    }
}

$graph = new Graph();
$graph->addEdge("A", "B");
$graph->addEdge("B", "C");
$graph->addEdge("C", "A");

print_r($graph->getGraph());

Примеры использования графов

1. Социальные сети: Графы используются для представления и анализа социальных сетей, где пользователи являются узлами, а их взаимоотношения — рёбрами. Например, в VK можно использовать граф для анализа связей между пользователями и предложения новых друзей.
2. Системы рекомендаций: В системах рекомендаций, например, на сайтах электронной коммерции или в стриминговых сервисах, графы могут использоваться для анализа предпочтений пользователя и рекомендации продуктов или контента.
3. Навигация и картография: В приложениях для карт и навигации, таких как Google Maps, графы используются для представления дорожных сетей, где узлы представляют перекрёстки, а рёбра — дороги. Алгоритмы поиска кратчайшего пути на графе помогают в планировании маршрутов.
4. Анализ сетевого трафика: Графы могут использоваться для моделирования и анализа сетевых структур, например, для обнаружения узких мест в сетевом трафике или для анализа распространения информации в сети.

Простая система рекомендации фильмов на PHP

// Определение класса Graph
class Graph {
    private $graph;

    // Конструктор для инициализации графа
    public function __construct() {
        $this->graph = [];
    }

    // Добавление связи между пользователем и фильмом
    public function addEdge($user, $movie) {
        $this->graph[$user][] = $movie;
    }

    // Получение связанных фильмов для пользователя
    public function getConnections($user) {
        return $this->graph[$user] ?? [];
    }
}

// Создание нового графа
$graph = new Graph();

// Добавление взаимодействий пользователей с фильмами
$graph->addEdge("User1", "Movie1");
$graph->addEdge("User1", "Movie2");
$graph->addEdge("User2", "Movie1");
$graph->addEdge("User2", "Movie3");
$graph->addEdge("User3", "Movie2");
$graph->addEdge("User3", "Movie3");

// Функция для рекомендации фильмов пользователю
function recommendMovies($graph, $currentUser) {
    // Получаем список фильмов, которые уже были просмотрены пользователем
    $watchedMovies = $graph->getConnections($currentUser);
    $recommendations = [];

    // Перебираем всех пользователей и их просмотренные фильмы
    foreach ($graph->graph as $user => $movies) {
        // Исключаем текущего пользователя из рассмотрения
        if ($user !== $currentUser) {
            // Находим общие фильмы между текущим пользователем и другими
            $commonMovies = array_intersect($movies, $watchedMovies);
            // Если есть общие фильмы
            if (count($commonMovies) > 0) {
                // Перебираем фильмы, просмотренные другим пользователем
                foreach ($movies as $movie) {
                    // Проверяем, не просмотрел ли текущий пользователь этот фильм
                    if (!in_array($movie, $watchedMovies)) {
                        // Добавляем или увеличиваем счетчик рекомендаций фильма
                        $recommendations[$movie] = ($recommendations[$movie] ?? 0) + 1;
                    }
                }
            }
        }
    }

    // Сортируем рекомендации по убыванию количества совпадений
    arsort($recommendations);
    // Возвращаем список рекомендованных фильмов
    return array_keys($recommendations);
}

// Получение рекомендаций для конкретного пользователя
$recommendedMovies = recommendMovies($graph, "User1");
print_r($recommendedMovies);

В этом коде мы создаем простую систему рекомендаций, основанную на графе взаимодействий пользователей с фильмами.

Функция recommendMovies анализирует граф, чтобы найти фильмы, которые могут быть интересны пользователю на основе его предыдущих просмотров и сходства с предпочтениями других пользователей.