Struktura danych wykresu jest zbiorem węzły połączony przez krawędzie . Służy do reprezentowania relacji między różnymi podmiotami. Algorytmy grafowe to metody stosowane do manipulowania i analizowania wykresów, rozwiązywania różnych problemów, takich jak znalezienie najkrótszej ścieżki Lub wykrywanie cykli.

liczba całkowita w porównaniu do Java

Spis treści

• Składniki wykresu
• Podstawowe operacje na wykresach
• Zastosowania wykresu
• Podstawy wykresu
• BFS i DFS na wykresie
• Cykle na wykresie
• Najkrótsza ścieżka na grafie
• Minimalne drzewo rozpinające
• Sortowanie topologiczne
• Łączność na wykresie
• Maksymalny przepływ na wykresie
• Niektórzy muszą rozwiązywać zadania na wykresie
• Niektóre quizy

Składniki wykresu:

• Wierzchołki: Wierzchołki są podstawowymi jednostkami grafu. Czasami wierzchołki są również nazywane wierzchołkami lub węzłami. Każdy węzeł/wierzchołek może być oznaczony lub nieoznaczony.
• Krawędzie: Krawędzie są rysowane lub używane do łączenia dwóch węzłów wykresu. Można uporządkować parę węzłów w grafie skierowanym. Krawędzie mogą łączyć dowolne dwa węzły w dowolny możliwy sposób. Nie ma zasad. Czasami krawędzie nazywane są również łukami. Każdą krawędź można oznaczyć/odpisać.

Podstawowe operacje na wykresach:

Poniżej znajdują się podstawowe operacje na wykresie:

• Wstawianie węzłów/krawędzi na wykresie – Wstaw węzeł na wykresie.
• Usuwanie węzłów/krawędzi na wykresie – Usuń węzeł z wykresu.
• Wyszukiwanie na wykresach – wyszukaj obiekt na wykresie.
• Przechodzenie przez wykresy – Przechodzenie przez wszystkie węzły na wykresie.

Zastosowania wykresu:

Poniżej znajdują się rzeczywiste zastosowania:

• Graficzne struktury danych można wykorzystać do przedstawienia interakcji między graczami w drużynie, takich jak podania, strzały i odbiory. Analiza tych interakcji może zapewnić wgląd w dynamikę zespołu i obszary wymagające poprawy.
• Powszechnie używany do reprezentowania sieci społecznościowych, takich jak sieci znajomych w mediach społecznościowych.
• Wykresy mogą służyć do przedstawiania topologii sieci komputerowych, np. połączeń między routerami i przełącznikami.
• Wykresy służą do przedstawiania połączeń między różnymi miejscami w sieci transportowej, takimi jak drogi i lotniska.
• Wykresy są używane w sieciach neuronowych, gdzie wierzchołki reprezentują neurony, a krawędzie reprezentują synapsy między nimi. Sieci neuronowe służą do zrozumienia, jak działa nasz mózg i jak zmieniają się połączenia, gdy się uczymy. Ludzki mózg ma około 10^11 neuronów i blisko 10^15 synaps.

Podstawy wykresu:

• Wprowadzenie do wykresów
• Wykres i jego reprezentacje
• Rodzaje wykresów z przykładami
• Podstawowe właściwości wykresu
• Zastosowania, zalety i wady wykresu
• Transponuj wykres
• Różnica między wykresem a drzewem

BFS i DFS na wykresie:

• Szerokość pierwszego przejścia dla wykresu
• Głębokość pierwszego przejścia dla wykresu
• Zastosowania wyszukiwania w głąb
• Zastosowania pierwszego przejścia wszerz
• Iteracyjne pierwsze przeszukiwanie głębokości
• BFS dla odłączonego wykresu
• Przechodnie zamknięcie wykresu przy użyciu DFS
• Różnica między BFS i DFS

Cykle na wykresie:

• Wykryj cykl na grafie skierowanym
• Wykryj cykl na grafie nieskierowanym
• Wykryj cykl na wykresie bezpośrednim za pomocą kolorów
• Wykryj cykl ujemny na wykresie | (Bellman Ford)
• Cykle o długości n w grafie nieskierowanym i spójnym
• Wykrywanie cyklu ujemnego przy użyciu Floyda Warshalla
• Klonuj ukierunkowany graf acykliczny
• Kompresja według rangi i ścieżki w algorytmie znajdowania Unii
• Najkrótsza ścieżka na wykresie:
  • Algorytm najkrótszej ścieżki Dijkstry
  • Algorytm Bellmana-Forda
  • Algorytm Floyda Warshalla
  • Algorytm Johnsona dla najkrótszych ścieżek wszystkich par
  • Najkrótsza ścieżka w ukierunkowanym grafie acyklicznym
  • Algorytm wybierania
  • Wykres wielostopniowy (najkrótsza ścieżka)
  • Najkrótsza ścieżka na grafie nieważonym
  • Algorytm minimalnego średniego (lub średniego) cyklu wagowego Karpa
  • 0-1 BFS (najkrótsza ścieżka na binarnym wykresie wagowym)
  • Znajdź minimalny cykl ciężaru na nieskierowanym wykresie

  Minimalne drzewo rozpinające:

  • Minimalne drzewo rozpinające Prima (MST)
  • Algorytm minimalnego drzewa rozpinającego Kruskala
  • Różnica między algorytmem Prima i Kruskala dla MST
  • Zastosowania problemu minimalnego drzewa rozpinającego
  • Minimalny koszt połączenia wszystkich miast
  • Całkowita liczba drzew opinających na wykresie
  • Minimalne drzewo opinające produkt
  • Odwróć algorytm usuwania dla minimalnego drzewa opinającego
  • Algorytm Boruvki dla minimalnego drzewa rozpinającego

  Sortowanie topologiczne:

  • Sortowanie topologiczne
  • Wszystkie topologiczne rodzaje skierowanego grafu acyklicznego
  • Algorytm Kahna sortowania topologicznego
  • Maksymalne krawędzie, które można dodać do DAG, tak aby pozostał DAG
  • Najdłuższa ścieżka w ukierunkowanym grafie acyklicznym
  • Topologiczne Sortowanie grafu na podstawie czasu wyjścia wierzchołka

  Łączność na wykresie:

  • Punkty artykulacyjne (lub wierzchołki wycięte) na wykresie
  • Podwójnie połączone komponenty
  • Mosty na wykresie
  • Droga i obwód Eulera
  • Algorytm Fleury’ego do drukowania ścieżki lub obwodu Eulera
  • Silnie połączone komponenty
  • Policz wszystkie możliwe przejścia od źródła do celu z dokładnie k krawędziami
  • Obwód Eulera w grafie skierowanym
  • Długość najkrótszego łańcucha umożliwiającego dotarcie do słowa docelowego
  • Sprawdź, czy tablicę ciągów można połączyć w okrąg
  • Algorytm Tarjana do wyszukiwania silnie połączonych komponentów
  • Ścieżki do pokonania każdego węzła przy użyciu każdej krawędzi (Siedem mostów Królewca)
  • Dynamiczna łączność | Zestaw 1 (przyrostowy)

  Maksymalny przepływ na wykresie:

  • Wprowadzenie do problemu maksymalnego przepływu
  • Algorytm Forda-Fulkersona dla problemu maksymalnego przepływu
  • Znajdź maksymalną liczbę rozłącznych ścieżek krawędziowych między dwoma wierzchołkami
  • Znajdź minimalne przecięcie s-t w sieci przepływowej
  • Maksymalne dopasowanie dwustronne
  • Problem z przypisaniem kanału
  • Wprowadzenie do algorytmu Push Relabel
  • Algorytm Kargera – zestaw 1 – wprowadzenie i wdrożenie
  • Algorytm Dinica dla maksymalnego przepływu

  Niektórzy muszą wykonać zadania na wykresie:

  • Znajdź długość największego obszaru w macierzy Boole’a
  • Policz liczbę drzew w lesie
  • Problem z wykresem Petersona
  • Klonuj graf nieskierowany
  • Kolorowanie wykresów (wprowadzenie i zastosowania)
  • Implementacja problemu komiwojażera (TSP).
  • Problem z pokryciem wierzchołków | Zestaw 1 (wprowadzenie i przybliżony algorytm)
  • Problem z centrami K | Zestaw 1 (zachłanny algorytm przybliżony)
  • Model Erdosa Renyla (do generowania losowych wykresów)
  • Chiński listonosz lub kontrola trasy | Zestaw 1 (wprowadzenie)
  • Algorytm Hierholzera dla grafu skierowanego
  • Sprawdź, czy dany graf jest dwudzielny, czy nie
  • Problem węża i drabiny
  • Boggle (Znajdź wszystkie możliwe słowa na tablicy znaków)
  • Algorytm Hopcrofta Karpa dla maksymalnego dopasowania – wprowadzenie
  • Minimalny czas gnicia wszystkich pomarańczy
  • Z podanych stopni wszystkich wierzchołków zbuduj graf
  • Ustal, czy w grafie skierowanym istnieje uniwersalny upływ
  • Liczba węzłów ujścia na wykresie
  • Problem dwóch klik (sprawdź, czy wykres można podzielić na dwie kliki)

  Niektóre quizy:

  • Quizy dotyczące poruszania się po grafie
  • Quizy na temat najkrótszej ścieżki wykresu
  • Quizy na temat minimalnego drzewa rozpinającego wykresu
  • Quizy dotyczące wykresów

  Szybkie linki :

  • 10 najpopularniejszych pytań podczas rozmowy kwalifikacyjnej dotyczących wyszukiwania w głąb (DFS)
  • Kilka interesujących pytań dotyczących najkrótszej ścieżki
  • Filmy na wykresach

  Zalecana:

  • Naucz się struktury danych i algorytmów | Poradnik DSA