Некоторые типы задач, которые можно решать с помощью графов:

• Поиск кратчайшего пути. 1 Например, алгоритм Дейкстры находит кратчайший путь из одной вершины до другой, если он существует. 1
• Поиск максимального потока. 1 С помощью этого алгоритма можно решить задачи максимальной пропускной способности трубопровода, дорожной или компьютерной сети. 1
• Поиск минимального остовного дерева. 1 Алгоритм ищет дерево минимального веса в графе, которое бы соединяло все вершины. 1 Например, с его помощью можно посчитать, где стоит проложить кабель, чтобы понадобилось минимальное количество кабеля. 1
• Распределение рабочих. 1 В распоряжении имеются N работников и M различных типов работ. 1 Разные работники могут выполнять разные типы работ. 1 Необходимо распределить работников, чтобы максимальное количество из них было занято. 1
• Популярность веб-сайтов. 1 Для составления рейтингов веб-сайтов поисковые системы часто учитывают, на какие сайты больше всего ссылаются другие сайты. 1 Для этого можно составить граф, где каждая дуга определяет ссылку одного сайта на другой. 1
• Рекомендация друзей. 1 Простейший алгоритм рекомендаций можно реализовать с помощью социального графа. 1
• Самый быстрый способ. 1 Например, добраться от дома до работы можно разными способами: поехать на машине, пойти пешком или воспользоваться самокатом. 1 Все эти действия можно представить в виде графа, где дугами будет являться продолжительность определённых действий. 1 Для поиска самого быстрого способа необходимо найти кратчайший путь между начальной и конечной вершиной. 1
• Комбинаторные задачи. 4 С помощью графов можно перебор и подсчёт различных комбинаций. 4