Автори:- Yash Gaherwar, Tanishq Deshpande, Devanshu Dalal, Avinash Dhakne

В тази статия ще обсъдим една от най-важните теми на „Анализ на дизайна на алгоритми“, т.е. Графика. Ще обсъдим различни алгоритми с тяхната стратегия за внедряване, анализ на сложността и приложения.

Какво е Graph?

Графиката е визуално представяне на колекция от неща, където някои двойки обекти са свързани заедно. Върховете са точките, използвани за изобразяване на взаимосвързаните елементи, докато ръбовете са връзките между тях.

Графът се дефинира формално като двойка множества (V, E), където V е множеството от върхове, а E е множеството от ребра, които свързват двойките върхове.

Какво е теория на графите?

Изследването на графиките е известно като „теория на графите“. Теорията на графите се фокусира върху това как ръбовете и върховете се отнасят един към друг. Това е много харесван предмет с приложения в области като компютърни науки, информационни технологии, бионауки и математика.

Представяне на графика:-

Има два различни начина за представяне на графики: -

  1. Матрица на съседство:-

→ Матрицата на съседство е форма на представяне в ред.
→ Използва се, за да покаже кои възли са близо един до друг. т.е. има ли графика ребра, които свързват възлите му.

→ Можем да запазим теглото на ръба вместо 1 и 0, ако графиката е претеглена.

2. Списък на съседство:-

→ Свързаното представяне се нарича списък на съседство.
→ В този модел ние следим съседите на всеки връх за всеки възел в графиката. В резултат на това всеки връх в мрежата има списък на върховете, които са непосредствено близо до него.
→ За всеки връх v, свързаният елемент от масив сочи към единично свързан списък от съседи на v. Масивът от върхове се индексира по номера на върховете.

Различни алгоритми за теория на графиките: -

1) Алгоритъм за първо търсене в дълбочина (DFS):-

→ Всеки връх на графиката е присвоен на една от двете категории в типична реализация на DFS: -

а) Посетен б) Непосетен.

Как работи DFS алгоритъмът:-

  1. Започнете с подреждането на всеки връх на графиката върху друг.
  2. Добавете елемента в горната част на стека към посетения списък.
  3. Направете списък на възлите, които са близо до този връх. Поставете елементите, които не са били посетени, в горната част на стека.
  4. Повторете действия 2 и 3, докато купчината изчезне напълно.

Анализ на сложността:-

(V-› върхове и E -› брой ръбове)

  1. Времева сложност на DFS:- O(V+E)
  2. Пространствена сложност на DFS:- O(V)

Приложения на DFS:-

  1. Цикъл на откриване
  2. За да определите дали една графика е двучастна или не.
  3. За идентифициране на силно свързани елементи на графиката (свързани компоненти).

2) Алгоритъм за първо търсене в ширина (BFS):-

Всеки връх на графиката е присвоен на една от двете категории в типично изпълнение на BFS: -

а) Посетен б) Непосетен.

Как работи алгоритъмът BFS:-

  1. Поставете който и да е връх на графиката в края на опашката, за да започнете.
  2. Добавете елемента в началото на реда към посетения списък.
  3. Направете списък на възлите, които са близо до този връх. Поставете елементите, които не са били посетени, в края на списъка.
  4. Повторете действия 2 и 3, докато линията се освободи.

Анализ на сложността:-

(V-› върхове и E -› брой ръбове)

  1. Времева сложност на DFS:- O(V+E)
  2. Пространствена сложност на DFS:- O(V)

Приложения на BFS:-

  1. За да създадете индекс за всяко търсене.
  2. Използва се в GPS навигационни алгоритми.
  3. Използвайки алгоритъма на Ford-Fulkerson, намерете максималния поток на мрежата.
  4. Откриване на цикъл в мрежа, която не е насочена.
  5. Минимално покриващо дърво.

3) Алгоритъмът на Белман Форд:-

Как работи алгоритъмът на Bellman Ford:-

→ Алгоритъмът на Bellman Ford функционира чрез надценяване на разстоянието между началния връх и всеки следващ връх.

→ След това, чрез разкриване на нови пътища, които са по-къси от остарелите, надценени пътища, той итеративно намалява тези оценки.

Анализ на сложността:-

(V-› върхове и E -› брой ръбове)

  1. Сложност в най-добрия случай:-O(E)
  2. Средна сложност на случая:- O(V*E)
  3. Сложност в най-лошия случай:- O(V*E)

→ Космическа сложност на Bellman Ford:- O(V)

Приложения на Bellman Ford:-

→ В алгоритмите за маршрутизиране, за определяне на най-кратките пътища.
→ За определяне на най-бързия маршрут.

4) Алгоритъм на Флойд-Уоршал:-

→ Алгоритъмът на Floyd-Warshall с претеглена графика се използва за определяне на най-краткия маршрут между всички двойки върхове.

→ Както в насочените, така и в неориентираните претеглени графики могат да бъдат решени с помощта на този подход.

→ Въпреки това, той е неефективен за графики с отрицателни цикли (където сумата от ребрата в цикъл е отрицателна).

Анализ на сложността:-

  1. Времева сложност на Floyd-Warshall:- O(n³)
  2. Космическа сложност на Флойд-Уоршал:- O(n²)

Приложения на Floyd-Warshall:-

  1. В насочен график, използван за определяне на най-краткия път.
  2. намерете транзитивното затваряне на насочените графи.
  3. Да се ​​определи инверсията на реалните матрици.
  4. За да се определи дали съществува двустранен неориентиран граф.

5) Алгоритъм на Prims:-

→ Той принадлежи към категория алгоритми, известни като алчни алгоритми, които намират локалния оптимум с намерението да намерят глобален оптимум.

→ Започвайки с един връх, продължаваме да добавяме ръбове с най-ниско тегло, докато постигнем целта си.

Как работи алгоритъмът Prims:-

Внедряването на алгоритъма на Prim включва следните стъпки:

  1. Настройте минималното обхващащо дърво, като използвате произволно избран връх.
  2. Намерете минимума от всички ръбове, свързващи дървото с нови върхове, след което го добавете към дървото.
  3. Повторете стъпка 2, ако е необходимо, за да получите минимално обхващащо дърво.

Анализ на сложността:-

(V-› върхове и E -› брой ръбове)

  1. Времева сложност на първичните числа:- O(E*log(V))

Приложения на Prims:-

  1. Монтаж на електрически кабели
  2. Мрежата е изградена за създаване на протоколи в мрежови цикли.

6) Алгоритъм на Kruskal:-

→ Той принадлежи към категория алгоритми, известни като алчни алгоритми, които намират локалния оптимум с намерението да намерят глобален оптимум.

→ Ръбовете с най-ниско тегло са мястото, където започваме, и продължаваме да добавяме ръбове, докато стигнем до нашата дестинация.

Как работи алгоритъмът Kruskal:-

Следват етапите за прилагане на алгоритъма на Kruskal:

  1. Подредете всеки ръб от лек до тежък.
  2. Добавете ръба към обхващащото дърво, което има най-ниско тегло.
  3. Отхвърлете този ръб, ако добавянето му доведе до цикъл.
  4. Докато достигнем всички върхове, продължавайте да добавяте ръбове.

Анализ на сложността:-

(V-› върхове и E -› брой ръбове)

  1. Времева сложност на първичните числа:- O(E*log(E))

Приложения на Kruskal:-

  1. Използва се при проектиране на електрически кабели.
  2. Работа в мрежа в компютри.

7) Алгоритъмът на Дейкстра: -

→ Можем да определим най-краткия маршрут между всеки два върха на графиката, използвайки подхода на Dijkstra. Тъй като не всички върхове на графиката могат да бъдат включени в най-късото разстояние между два върха, то е различно от минималното обхващащо дърво.

Анализ на сложността:-

(V-› върхове и E -› брой ръбове)

  1. Времева сложност на алгоритъма на Дейкстра: - O(E*log(V))
  2. Пространствена сложност на алгоритъма на Дейкстра:- O(V)

Приложения на алгоритъма на Дейкстра:-

  1. За определяне на най-бързия маршрут
  2. В приложения за социални мрежи
  3. Използва се в рамките на телефонна мрежа.
  4. Използва се за локализиране на местата на картата.

Различни приложения на теорията на графите: -

1) Проектирането на верижни връзки често използва принципите на теорията на графите в електротехниката. Топологиите се отнасят до разновидностите или конфигурациите на връзките. Звезда, мост, серия и паралелни топологии са няколко примера за топологии.

2) За изучаване на алгоритми се използва Теорията на графите. Малко алгоритми са Prims, Kruskals и Dijkstra.

3) В CN (компютърна мрежа) теорията на графите се използва за обяснение на връзките между свързаните машини в мрежата.

4) В науката графиките се използват за представяне на молекулната структура, химическата структура, структурата на ДНК и други физични свойства на веществата.

5) Общите графики могат да се използват за показване на маршрутите между градовете. Специален вид графика, наречена „дърво“, може да се използва за представяне на йерархично подредена информация, като родословно дърво.

Заключение: -

От тук можем да заключим, че Графиката е една от много интересните и важни Разширени структури на данни, която се използва широко и в индустрията. Теорията на графите дава възможност да се гарантира надеждна услуга, например в навигационните услуги, включително Google Maps и други. И всяка секунда го използваме, независимо дали под формата на социална мрежа или като го прилагаме. В тази статия научихме за различни техники за алгоритми на графики с тяхната сложност и стратегии за прилагане.