➡️ Стартуем тему графов

Представь большую карту страны:
▫Граф — это как схема всех дорог страны
▫Вершина графа — город на карте
▫Ребро графа — дорога между городами

➖Вес ребра — может быть расстоянием в километрах, временем в пути или стоимостью билета
➖Направленные рёбра — если дорога односторонняя
➖Ненаправленные рёбра — обычная дорога, по которой можно ездить в обе стороны

С таким графом можно:
▫Найти кратчайший путь между городами (как в навигаторе)
▫Определить, можно ли проехать из одного города в другой (проверить связность)
▫Построить маршрут, который проходит через все нужные города

🟦Основные алгоритмы для обхода графов это DFS и BFS

✅ DFS (Depth-first search)
Ты путешествуешь вглубь, сначала исследуешь одну ветку дорог до конца, а потом возвращаешься:

🟪Начинаешь с первого города
🟪Выбираешь первую дорогу, которая ведёт куда-то ещё и едешь туда
🟪В новом городе снова выбираешь первую доступную дорогу и так, пока не приедешь в тупик или в город, в котором уже был
🟪Если упёрся — возвращаешься назад в предыдущий город и пробуешь другую дорогу

✅ BFS (Breadth-first search)
Ты путешествуешь по слоям, сначала посещая все города поближе, потом всё дальше и дальше:

▫Начинаешь с первого города
▫Сначала смотришь все соседние города и отмечаешь их, как «следующие в очереди»
▫Затем посещаешь все города на расстоянии 1 дороги, потом на расстоянии 2 дорог, потом 3 и так далее

#graphs

🟢Easy
1971. Find if Path Exists in Graph

Company: 🔍📱📱

📝Дан граф с n вершинами, где каждая вершина помечена от 0 до n-1.

Ребра графа представлены двумерным массивом целых чисел edges, где edges[i] обозначает двунаправленное ребро между вершинами. Каждая пара вершин соединена не более чем одним ребром, и ни одна вершина не имеет ребра, ведущего в себя.

Верните true, если существует допустимый путь от вершины source к вершине destination

💡: используйте Map для удобного представления графа

#leetcode1971 | #easy #graphs

🟢Easy
1791. Find Center of Star Graph

Company: 🔍📱📕

📝Дан неориентированный звёздчатый граф, состоящий из n узлов, помеченных от 1 до n. Верните центр заданного звёздного графа.

Граф представлен двумерным массивом целых чисел edges, где edges[i] указывает на ребро между вершинами.

Ограничения:

3 <= n <= 10^5
edges.length == n - 1

💡: используйте главную особенность центра графа

#leetcode1791 | #easy #graphs

🟡Medium
886. Possible Bipartition

Company: 📕✴️📱

📝Дано число n и массив dislikes, где dislikes[i] = [aᵢ, bᵢ] — пары людей, которые не ладят между собой.

Верните true, если можно разделить всех n человек на две группы так, чтобы ни одна пара из dislikes не оказалась в одной группе

💡: используйте алгоритмы обхода, чтобы поочерёдно назначать людям противоположные группы и выявлять возможные конфликты

#leetcode886 | #medium #graphs

🟡Medium
210. Course Schedule II

Company: 🚔✴️📱

📝Вам дан массив prerequisites, где prerequisites[i] = [ai, bi] означает, что для прохождения курса ai необходимо сначала пройти курс bi.

Верните порядок курсов, которые необходимо пройти, чтобы закончить их все. Если допустимых ответов несколько, верните любой из них. Если невозможно закончить все курсы, верните пустой массив

💡: помечайте курсы во время обхода, чтобы обнаружить циклы

#leetcode210 | #medium #graphs

🟡Medium
1136. Parallel Courses

Company: 📕🔍🚖

📝Дано n курсов и список зависимостей relations, где каждая пара [a, b] означает: курс a должен быть пройден до курса b.

За один семестр можно брать любое количество курсов, если все нужные для них предыдущие курсы уже пройдены.

Нужно вернуть минимальное число семестров, чтобы пройти все курсы, или -1, если пройти все курсы невозможно

💡: начните обход с курсов, у которых нет зависимостей, затем освобождайте следующие и так далее

#leetcode1136 | #medium #graphs