Структура даних графа є колекцією вузлів пов'язаний краю . Він використовується для представлення зв’язків між різними об’єктами. Графові алгоритми це методи, які використовуються для обробки та аналізу графіків, вирішення різноманітних проблем, як-от знаходження найкоротшого шляху або виявлення циклів.

для кожного машинопису

Зміст

• Компоненти графа
• Основні операції над графіками
• Застосування Graph
• Основи графіка
• BFS і DFS на графіку
• Цикли в графі
• Найкоротший шлях у графіку
• Мінімальне охоплююче дерево
• Топологічне сортування
• Підключення в Graph
• Максимальний потік на графіку
• Деякі повинні виконувати завдання на графіку
• Деякі вікторини

Компоненти графіка:

• Вершини: Вершини є фундаментальними одиницями графа. Іноді вершини також називаються вершинами або вузлами. Кожен вузол/вершина може бути позначений або не позначений.
• Краї: Ребра малюються або використовуються для з’єднання двох вузлів графа. Можна впорядкувати пару вузлів у орієнтований граф. Ребра можуть з'єднувати будь-які два вузли будь-яким можливим способом. Правил немає. Іноді ребра також називаються дугами. Кожне ребро можна позначити/зняти з міток.

Основні операції над графіками:

Нижче наведено основні операції над графіком:

• Вставлення вузлів/ребер у граф – вставте вузол у графік.
• Видалення вузлів/ребер на графіку – видалення вузла з графіка.
• Пошук на графіках – пошук сутності на графіку.
• Обхід графів – обхід усіх вузлів на графіку.

Застосування Graph:

Нижче наведено реальні програми:

• Графічні структури даних можна використовувати для представлення взаємодії між гравцями в команді, як-от передачі, удари та підбори. Аналіз цих взаємодій може дати розуміння динаміки команди та областей, які потрібно вдосконалити.
• Зазвичай використовується для представлення соціальних мереж, наприклад мереж друзів у соціальних мережах.
• Графи можна використовувати для представлення топології комп’ютерних мереж, наприклад з’єднань між маршрутизаторами та комутаторами.
• Графіки використовуються для представлення зв’язків між різними місцями транспортної мережі, такими як дороги та аеропорти.
• Графи використовуються в нейронних мережах, де вершини представляють нейрони, а ребра — синапси між ними. Нейронні мережі використовуються, щоб зрозуміти, як працює наш мозок і як змінюються зв’язки, коли ми навчаємося. Людський мозок має близько 10^11 нейронів і близько 10^15 синапсів.

Основи графіка:

• Введення в графіки
• Граф та його зображення
• Типи графіків з прикладами
• Основні властивості графа
• Застосування, переваги та недоліки Graph
• Транспонувати граф
• Різниця між графом і деревом

BFS і DFS на графіку:

• Перший обхід у ширину для графіка
• Перший обхід глибини для графіка
• Застосування пошуку в глибину
• Застосування обходу в ширину
• Ітеративний пошук глибини
• BFS для відключеного графа
• Транзитивне замикання графа за допомогою DFS
• Різниця між BFS і DFS

Цикли в графі:

• Виявлення циклу в орієнтованому графі
• Виявлення циклу в неорієнтованому графі
• Виявлення циклу в прямому графіку за допомогою кольорів
• Виявлення негативного циклу на графіку | (Беллман Форд)
• Цикли довжини n в неорієнтованому та зв’язному графі
• Виявлення негативного циклу за допомогою Floyd Warshall
• Клонуйте орієнтований ациклічний граф
• Об’єднання за рангом і стиснення шляху в алгоритмі об’єднання
• Найкоротший шлях у графіку:
  • Алгоритм найкоротшого шляху Дейкстри
  • Алгоритм Беллмана–Форда
  • Алгоритм Флойда Воршелла
  • Алгоритм Джонсона для всіх пар найкоротших шляхів
  • Найкоротший шлях у спрямованому ациклічному графі
  • Алгоритм набору
  • Багатоетапний графік (найкоротший шлях)
  • Найкоротший шлях у незваженому графі
  • Алгоритм циклу мінімальної середньої (або середньої) ваги Карпа
  • 0-1 BFS (найкоротший шлях у бінарному ваговому графіку)
  • Знайдіть цикл мінімальної ваги в неорієнтованому графі

  Мінімальне охоплююче дерево:

  • Мінімальне остовне дерево Prim (MST)
  • Алгоритм мінімального остовного дерева Крускала
  • Різниця між алгоритмом Пріма та Крускала для MST
  • Застосування проблеми мінімального остовного дерева
  • Мінімальна вартість підключення всіх міст
  • Загальна кількість охоплюючих дерев у графі
  • Мінімальне охоплююче дерево продукту
  • Алгоритм зворотного видалення для мінімального охоплюючого дерева
  • Алгоритм Борувки для мінімального остовного дерева

  Топологічне сортування:

  • Топологічне сортування
  • Усі топологічні види орієнтованого ациклічного графа
  • Алгоритм Кана для топологічного сортування
  • Максимальна кількість ребер, які можна додати до DAG, щоб він залишався DAG
  • Найдовший шлях у спрямованому ациклічному графі
  • Топологічний сорт графа за часом відправлення вершини

  Підключення в графі:

  • Точки артикуляції (або розрізані вершини) у графі
  • Двозв’язні компоненти
  • Мости в графі
  • Ейлерів шлях і контур
  • Алгоритм Флері для друку Ейлерового шляху або схеми
  • Сильно пов'язані компоненти
  • Підрахуйте всі можливі шляхи від джерела до пункту призначення з рівно k ребрами
  • Контур Ейлера в орієнтованому графі
  • Довжина найкоротшого ланцюжка для досягнення цільового слова
  • Знайдіть, чи можна об’єднати масив рядків у коло
  • Алгоритм Тар’яна для пошуку міцно зв’язаних компонентів
  • Шляхи для кожного вузла, використовуючи кожне ребро (Сім мостів Кенігсберга)
  • Динамічний зв'язок | Набір 1 (інкрементальний)

  Максимальний потік на графіку:

  • Вступ до проблеми максимального потоку
  • Алгоритм Форда-Фулкерсона для проблеми максимального потоку
  • Знайдіть максимальну кількість непересічних шляхів між двома вершинами
  • Знайти мінімальний с-т перерізу потокової мережі
  • Максимальна дводольна відповідність
  • Проблема призначення каналу
  • Вступ до алгоритму Push Relabel
  • Алгоритм Каргера - Набір 1 - Введення та реалізація
  • Алгоритм Дініка для максимального потоку

  Деякі повинні виконувати задачі на графіку:

  • Знайдіть довжину найбільшої області в булевій матриці
  • Підрахувати кількість дерев у лісі
  • Граф Петерсона
  • Клонуйте неорієнтований граф
  • Розфарбовування графів (вступ і застосування)
  • Реалізація проблеми комівояжера (TSP).
  • Проблема покриття вершини | Набір 1 (Вступ і приблизний алгоритм)
  • Проблема центрів K | Набір 1 (Жадібний наближений алгоритм)
  • Модель Erdos Renyl (для генерації випадкових графіків)
  • Китайський листоноша або інспекція маршруту | Комплект 1 (введення)
  • Алгоритм Ієргольцера для орієнтованого графа
  • Перевірте, чи є даний граф дводольним чи ні
  • Проблема «Змія та драбина».
  • Boggle (знайти всі можливі слова на дошці символів)
  • Алгоритм Гопкрофта Карпа для максимальної відповідності - Вступ
  • Мінімальний час для гниття всіх апельсинів
  • Побудуйте граф за заданими степенями всіх вершин
  • Визначте, чи існує універсальний сток в орієнтованому графі
  • Кількість вузлів приймача в графі
  • Проблема двох клік (перевірте, чи можна розділити графік на дві кліки)

  Деякі тести:

  • Тести з обходу графа
  • Тести на графік найкоротшого шляху
  • Тести з мінімального остовного дерева графа
  • Тести про графіки

  Швидкі посилання:

  • 10 найпопулярніших запитань на співбесіді про Depth First Search (DFS)
  • Деякі цікаві питання про найкоротший шлях
  • Відео про графіки

  Рекомендовано:

  • Вивчіть структуру даних і алгоритми | Підручник DSA