algorithm
Wykres

Wprowadzenie

Uwagi

Sortowanie topologiczne

Porządkowanie topologiczne lub rodzaj topologiczny porządkuje wierzchołki na ukierunkowanym wykresie acyklicznym na linii, tj. Na liście, tak aby wszystkie skierowane krawędzie przebiegały od lewej do prawej. Takie uporządkowanie nie może istnieć, jeśli wykres zawiera ukierunkowany cykl, ponieważ nie ma sposobu, abyś mógł iść prosto na linii i nadal powrócić do miejsca, z którego zacząłeś.

Formalnie na wykresie G = (V, E) , wówczas liniowe uporządkowanie wszystkich jego wierzchołków jest takie, że jeśli G zawiera krawędź (u, v) ∈ E od wierzchołka u do wierzchołka v to u poprzedza v w porządku.

Należy zauważyć, że każdy DAG ma co najmniej jeden rodzaj topologiczny.

Znane są algorytmy konstruowania uporządkowania topologicznego dowolnego DAG w czasie liniowym, jednym z przykładów jest:

1. Wywołaj depth_first_search(G) aby obliczyć czasy zakończenia vf dla każdego wierzchołka v
2. Po zakończeniu każdego wierzchołka wstaw go na początku połączonej listy
3. połączona lista wierzchołków, ponieważ jest ona teraz posortowana.

Sortowanie topologiczne można wykonać w czasie ϴ(V + E) , ponieważ algorytm wyszukiwania w pierwszej głębokości zajmuje czas ϴ(V + E) i zajmuje Ω(1) (czas stały), aby wstawić każdy z |V| wierzchołki na początku połączonej listy.

Wiele aplikacji używa ukierunkowanych wykresów acyklicznych do wskazywania pierwszeństwa między zdarzeniami. Używamy sortowania topologicznego, aby uzyskać porządek przetwarzania każdego wierzchołka przed dowolnym z jego następców.

Wierzchołki na wykresie mogą reprezentować zadania do wykonania, a krawędzie mogą stanowić ograniczenia, że jedno zadanie musi być wykonane przed drugim; uporządkowanie topologiczne jest prawidłową sekwencją do wykonywania zestawu zadań zadań opisanych w V

Instancja problemu i jego rozwiązanie

Niech wierzchołek v opisuje Task(hours_to_complete: int) , tj. Task(4) opisuje Task które zajmuje 4 godziny, a krawędź e opisuje Cooldown(hours: int) tak że Cooldown(3) opisuje czas trwania czas na ostygnięcie po ukończonym zadaniu.

Niech nasz wykres nazywa się dag (ponieważ jest to ukierunkowany wykres acykliczny) i niech zawiera 5 wierzchołków:

A <- dag.add_vertex(Task(4)); 
B <- dag.add_vertex(Task(5));
C <- dag.add_vertex(Task(3)); 
D <- dag.add_vertex(Task(2));
E <- dag.add_vertex(Task(7));

gdzie łączymy wierzchołki z ukierunkowanymi krawędziami tak, że wykres jest acykliczny,

// A ---> C ----+
// |      |     |
// v      v     v
// B ---> D --> E
dag.add_edge(A, B, Cooldown(2));
dag.add_edge(A, C, Cooldown(2));
dag.add_edge(B, D, Cooldown(1));
dag.add_edge(C, D, Cooldown(1));
dag.add_edge(C, E, Cooldown(1));
dag.add_edge(D, E, Cooldown(3));

wtedy są trzy możliwe porządki topologiczne między A i E ,

1. A -> B -> D -> E
2. A -> C -> D -> E
3. A -> C -> E

Algorytm Thorupa

Algorytm Thorupa dla najkrótszej ścieżki z jednego źródła dla niekierowanego wykresu ma złożoność czasową O (m), niższą niż Dijkstra.

Podstawowe pomysły są następujące. (Przepraszam, nie próbowałem go jeszcze wdrożyć, więc mogę pominąć kilka drobnych szczegółów. Oryginalny dokument jest zaplombowany, więc próbowałem go zrekonstruować z innych źródeł, które go dotyczą. Usuń ten komentarz, jeśli możesz to zweryfikować).

• Istnieją sposoby znalezienia drzewa opinającego w O (m) (nie opisane tutaj). Musisz „wyhodować” drzewo rozpinające od najkrótszej krawędzi do najdłuższej, a byłby to las z kilkoma połączonymi komponentami, zanim będzie w pełni rozwinięty.
• Wybierz liczbę całkowitą b (b> = 2) i rozważ tylko lasy rozciągające się z ograniczeniem długości b ^ k. Scal komponenty, które są dokładnie takie same, ale z innym k, i nazwij minimum k poziomem komponentu. Następnie logicznie przekształć komponenty w drzewo. u jest rodzicem v iff u jest najmniejszym składnikiem różnym od v, który w pełni zawiera v. Korzeń jest całym wykresem, a liście są pojedynczymi wierzchołkami na oryginalnym wykresie (z poziomem ujemnej nieskończoności). Drzewo nadal ma tylko O (n) węzłów.
• Zachowaj odległość każdego komponentu od źródła (jak w algorytmie Dijkstry). Odległość komponentu z więcej niż jednym wierzchołkiem jest minimalną odległością jego nierozwiniętych potomków. Ustaw odległość wierzchołka źródłowego na 0 i odpowiednio zaktualizuj przodków.
• Rozważ odległości w podstawie b. Odwiedzając węzeł na poziomie k po raz pierwszy, umieść jego dzieci w segmentach wspólnych dla wszystkich węzłów poziomu k (jak w sortowaniu kubełkowym, zastępując stertę w algorytmie Dijkstry) cyfrą k i większą jego odległością. Za każdym razem, gdy odwiedzasz węzeł, rozważ tylko jego pierwsze pakiety b, odwiedź i usuń każdy z nich, zaktualizuj odległość bieżącego węzła i ponownie połącz bieżący węzeł z jego własnym rodzicem, używając nowej odległości i poczekaj na następną wizytę na następną wiadra
• Podczas odwiedzania liścia aktualna odległość jest końcową odległością wierzchołka. Rozwiń wszystkie krawędzie na oryginalnym wykresie i odpowiednio zaktualizuj odległości.
• Odwiedzaj węzeł główny (cały wykres) wielokrotnie, aż do osiągnięcia celu.

Opiera się na fakcie, że nie ma krawędzi o długości mniejszej niż l pomiędzy dwoma połączonymi komponentami lasu rozpinającego z ograniczeniem długości l, więc zaczynając od odległości x, możesz skupić się tylko na jednym podłączonym komponencie, aż dotrzesz odległość x + l. Odwiedzisz niektóre wierzchołki, zanim wszystkie wierzchołki o krótszej odległości zostaną odwiedzone, ale to nie ma znaczenia, ponieważ wiadomo, że z tych wierzchołków nie będzie tutaj krótszej ścieżki. Inne części działają jak sortowanie kubełkowe / sortowanie MSD radix, i oczywiście wymaga drzewa opinającego O (m).

Wykrywanie cyklu na ukierunkowanym wykresie za pomocą głębokości pierwszego przejścia

Cykl na grafie skierowanym istnieje, jeśli podczas DFS wykryto tylną krawędź. Tylna krawędź to krawędź od węzła do siebie lub jednego z przodków w drzewie DFS. W przypadku odłączonego wykresu otrzymujemy las DFS, więc musisz iterować wszystkie wierzchołki na wykresie, aby znaleźć rozłączne drzewa DFS.

Implementacja C ++:

    #include <iostream>
     #include <list>
        
    using namespace std; 
    
    #define NUM_V   4

    bool helper(list<int> *graph, int u, bool* visited, bool* recStack)
    {
        visited[u]=true;
        recStack[u]=true;
        list<int>::iterator i;
        for(i = graph[u].begin();i!=graph[u].end();++i)
        {  
            if(recStack[*i]) //if vertice v is found in recursion stack of this DFS traversal
                return true;
            else if(*i==u) //if there's an edge from the vertex to itself
                return true;
            else if(!visited[*i])
            {   if(helper(graph, *i, visited, recStack))
                   return true;
            }
        }
        recStack[u]=false;
        return false;
    }
    /*
    /The wrapper function calls helper function on each vertices which have not been visited. Helper function returns true if it detects a back edge in the subgraph(tree) or false.
*/
    bool isCyclic(list<int> *graph, int V)
    {
      bool visited[V];  //array to track vertices already visited
      bool recStack[V]; //array to track vertices in recursion stack of the traversal.

      for(int i = 0;i<V;i++)
       visited[i]=false, recStack[i]=false;  //initialize all vertices as not visited and not recursed

      for(int u = 0; u < V; u++) //Iteratively checks if every vertices have been visited
      {   if(visited[u]==false)
          {  if(helper(graph, u, visited, recStack)) //checks if the DFS tree from the vertex contains a cycle
               return true;
          }
      }
       return false;
    }
    /*
    Driver function
    */
    int main()
    {
        list<int>* graph = new list<int>[NUM_V];
        graph[0].push_back(1);
        graph[0].push_back(2);
        graph[1].push_back(2);
        graph[2].push_back(0);
        graph[2].push_back(3);
        graph[3].push_back(3);
        bool res = isCyclic(graph, NUM_V);
        cout<<res<<endl;
    }

Wynik: jak pokazano poniżej, na wykresie znajdują się trzy tylne krawędzie. Jeden między wierzchołkiem 0 i 2; między wierzchołkiem 0, 1 i 2; i wierzchołek 3. Złożoność czasowa wyszukiwania wynosi O (V + E), gdzie V to liczba wierzchołków, a E to liczba krawędzi.

Wprowadzenie do teorii grafów

Teoria grafów to badanie grafów, które są strukturami matematycznymi stosowanymi do modelowania parowania relacji między obiektami.

Czy wiesz, że prawie wszystkie problemy na Ziemi można przekształcić w problemy Dróg i Miast i rozwiązać? Teoria grafów została wynaleziona wiele lat temu, jeszcze przed wynalezieniem komputera. Leonhard Euler napisał artykuł na temat siedmiu mostów z Królewca, który jest uważany za pierwszy artykuł teorii grafów. Od tego czasu ludzie zdali sobie sprawę, że jeśli uda nam się przekonwertować jakikolwiek problem na ten problem z drogą miejską, możemy go łatwo rozwiązać za pomocą teorii wykresów.

Teoria grafów ma wiele zastosowań. Jedną z najczęstszych jest znalezienie najkrótszej odległości między miastami. Wszyscy wiemy, że aby dotrzeć do twojego komputera, ta strona musiała podróżować z wielu routerów z serwera. Teoria wykresów pomaga znaleźć routery, które musiały zostać przekroczone. Podczas wojny, która ulica musi zostać zbombardowana, aby odłączyć stolicę od innych, to również można znaleźć za pomocą Teorii Grafów.

Nauczmy się najpierw kilku podstawowych definicji teorii grafów.

Wykres:

Powiedzmy, że mamy 6 miast. Oznaczamy je jako 1, 2, 3, 4, 5, 6. Teraz łączymy miasta, które mają drogi między sobą.

To prosty wykres, na którym pokazano niektóre miasta wraz z łączącymi je drogami. W teorii wykresów każde z tych miast nazywamy Węzłem lub Wierzchołkiem, a drogi nazywamy Krawędzią. Wykres jest po prostu połączeniem tych węzłów i krawędzi.

Węzeł może reprezentować wiele rzeczy. Na niektórych wykresach węzły przedstawiają miasta, niektóre przedstawiają lotniska, niektóre przedstawiają kwadrat na szachownicy. Edge reprezentuje relację między każdym węzłem. Relacją tą może być czas przejścia z jednego lotniska na drugie, ruchy rycerza z jednego kwadratu na wszystkie pozostałe kwadraty itp.

Ścieżka rycerza w szachownicy

Krótko mówiąc, Węzeł reprezentuje dowolny obiekt, a Krawędź reprezentuje relację między dwoma obiektami.

Sąsiedni węzeł:

Jeśli węzeł A dzieli krawędź z węzłem B , wówczas B uważa się za sąsiadujące z A. Innymi słowy, jeśli dwa węzły są bezpośrednio połączone, nazywane są węzłami sąsiednimi. Jeden węzeł może mieć wiele sąsiadujących węzłów.

Kierowany i nieukierowany wykres:

Na ukierunkowanych wykresach krawędzie mają znaki kierunkowe z jednej strony, co oznacza, że krawędzie są jednokierunkowe . Z drugiej strony krawędzie niekierowanych wykresów mają znaki kierunkowe po obu stronach, co oznacza, że są one dwukierunkowe . Zwykle niekierowane wykresy są przedstawiane bez znaków po obu stronach krawędzi.

Załóżmy, że trwa impreza. Ludzie w drużynie są reprezentowani przez węzły i między dwojgiem ludzi jest przewaga, jeśli podają sobie ręce. Następnie ten wykres nie jest przekierowywany, ponieważ każda osoba A podaje ręce osobie B wtedy i tylko wtedy, gdy B również podaje rękę A. W przeciwieństwie do tego, gdy krawędzie od osoby A, do drugiego odpowiada osoba B do A „s Admiring B, to wykres jest skierowane, ponieważ podziwa niekoniecznie jest ruchem posuwisto-zwrotnym. Pierwszy typ wykresu nazywany jest niekierowanym wykresem, a krawędzie nazywane są niekierowanymi krawędziami, podczas gdy drugi rodzaj wykresu nazywany jest wykresem ukierunkowanym, a krawędzie nazywane są skierowanymi krawędziami.

Wykres ważony i nieważony:

Wykres ważony to wykres, na którym do każdej krawędzi przypisana jest liczba (waga). Takie ciężary mogą reprezentować na przykład koszty, długości lub pojemności, w zależności od danego problemu.

Nieważony wykres jest wprost przeciwny. Zakładamy, że ciężar wszystkich krawędzi jest taki sam (przypuszczalnie 1).

Ścieżka:

Ścieżka reprezentuje sposób przejścia z jednego węzła do drugiego. Składa się z sekwencji krawędzi. Między dwoma węzłami może istnieć wiele ścieżek.

W powyższym przykładzie istnieją dwie ścieżki od A do D. A-> B, B-> C, C-> D to jedna ścieżka. Koszt tej ścieżki wynosi 3 + 4 + 2 = 9 . Znów jest inna ścieżka A-> D. Koszt tej ścieżki wynosi 10 . Ścieżka o najniższym koszcie nazywa się ścieżką najkrótszą .

Stopień:

Stopień wierzchołka to liczba krawędzi, które są z nim połączone. Jeśli jakaś krawędź łączy się z wierzchołkiem na obu końcach (pętla) jest liczona dwukrotnie.

Na wykresach ukierunkowanych węzły mają dwa typy stopni:

• Stopień: liczba krawędzi wskazujących na węzeł.
• Out-stopień: Liczba krawędzi, które wskazują od węzła do innych węzłów.

W przypadku wykresów bezkierunkowych są one po prostu nazywane stopniami.

Niektóre algorytmy związane z teorią grafów

• Algorytm Bellmana-Forda
• Algorytm Dijkstry
• Algorytm Forda-Fulkersona
• Algorytm Kruskala
• Algorytm najbliższego sąsiada
• Algorytm Prim
• Głębokie wyszukiwanie
• Pierwsze wyszukiwanie szerokości

Przechowywanie wykresów (macierz adiakencji)

Do przechowywania wykresu powszechne są dwie metody:

• Macierz sąsiedztwa
• Lista adiakencji

Macierz przylegania jest kwadratową macierzą używaną do przedstawienia skończonego wykresu. Elementy macierzy wskazują, czy pary wierzchołków sąsiadują czy nie na wykresie.

Przyleganie oznacza „obok lub przylega do czegoś innego” lub być obok czegoś. Na przykład sąsiedzi sąsiadują z tobą. W teorii grafów, jeśli możemy przejść do węzła B z węzła A , możemy powiedzieć, że węzeł B sąsiaduje z węzłem A. Teraz dowiemy się, jak przechowywać, które węzły przylegają do któregoś za pomocą macierzy adiakencji. Oznacza to, że będziemy reprezentować, które węzły dzielą krawędź między nimi. Tutaj macierz oznacza tablicę 2D.

Tutaj możesz zobaczyć tabelę obok wykresu, to jest nasza macierz przylegania. Tutaj macierz [i] [j] = 1 oznacza, że istnieje krawędź między i i j . Jeśli nie ma krawędzi, po prostu wstawiamy Matrix [i] [j] = 0 .

Te krawędzie mogą być ważone, tak jak mogą reprezentować odległość między dwoma miastami. Następnie wstawimy wartość do Matrycy [i] [j] zamiast 1.

Wykres opisany powyżej jest Dwukierunkowy lub Nieukierowany , co oznacza, że jeśli możemy przejść do węzła 1 z węzła 2 , możemy również przejść do węzła 2 z węzła 1 . Jeśli wykres został skierowany, to nie byłby już znak strzałki na jednej stronie wykresu. Nawet wtedy możemy to przedstawić za pomocą macierzy przyległości.

Reprezentujemy węzły, które nie dzielą krawędzi przez nieskończoność . Należy zauważyć, że jeżeli wykres nie jest przekierowany, macierz staje się symetryczna .

Pseudo-kod do utworzenia macierzy:

Procedure AdjacencyMatrix(N):    //N represents the number of nodes
Matrix[N][N]
for i from 1 to N
    for j from 1 to N
        Take input -> Matrix[i][j]
    endfor
endfor

Możemy również wypełnić Matrix w następujący sposób:

Procedure AdjacencyMatrix(N, E):    // N -> number of nodes
Matrix[N][E]                        // E -> number of edges
for i from 1 to E
    input -> n1, n2, cost
    Matrix[n1][n2] = cost
    Matrix[n2][n1] = cost
endfor

W przypadku grafów ukierunkowanych możemy usunąć macierz [n2] [n1] = linia kosztów .

Wady stosowania Matrycy Adiakencji:

Pamięć to ogromny problem. Bez względu na liczbę krawędzi zawsze będziemy potrzebować macierzy o rozmiarze N * N, gdzie N jest liczbą węzłów. Jeśli istnieje 10000 węzłów, rozmiar matrycy wyniesie 4 * 10000 * 10000 około 381 megabajtów. To ogromne marnotrawstwo pamięci, jeśli weźmiemy pod uwagę wykresy o kilku krawędziach.

Załóżmy, że chcemy dowiedzieć się, do którego węzła możemy przejść z węzła u . Musimy sprawdzić cały rząd u , co kosztuje dużo czasu.

Jedyną korzyścią jest to, że możemy łatwo znaleźć połączenie między węzłami UV i ich koszt za pomocą Matrycy Adiakencji.

Kod Java zaimplementowany przy użyciu powyższego pseudokodu:

import java.util.Scanner;
 
public class Represent_Graph_Adjacency_Matrix 
{
    private final int vertices;
    private int[][] adjacency_matrix;
 
    public Represent_Graph_Adjacency_Matrix(int v) 
    {
        vertices = v;
        adjacency_matrix = new int[vertices + 1][vertices + 1];
    }
 
    public void makeEdge(int to, int from, int edge) 
    {
        try 
        {
            adjacency_matrix[to][from] = edge;
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
    }
 
    public int getEdge(int to, int from) 
    {
        try 
        {
            return adjacency_matrix[to][from];
        }
        catch (ArrayIndexOutOfBoundsException index) 
        {
            System.out.println("The vertices does not exists");
        }
        return -1;
    }
 
    public static void main(String args[]) 
    {
        int v, e, count = 1, to = 0, from = 0;
        Scanner sc = new Scanner(System.in);
        Represent_Graph_Adjacency_Matrix graph;
        try 
        {
            System.out.println("Enter the number of vertices: ");
            v = sc.nextInt();
            System.out.println("Enter the number of edges: ");
            e = sc.nextInt();
 
            graph = new Represent_Graph_Adjacency_Matrix(v);
 
            System.out.println("Enter the edges: <to> <from>");
            while (count <= e) 
            {
                to = sc.nextInt();
                from = sc.nextInt();
 
                graph.makeEdge(to, from, 1);
                count++;
            }
 
            System.out.println("The adjacency matrix for the given graph is: ");
            System.out.print("  ");
            for (int i = 1; i <= v; i++)
                System.out.print(i + " ");
            System.out.println();
 
            for (int i = 1; i <= v; i++) 
            {
                System.out.print(i + " ");
                for (int j = 1; j <= v; j++) 
                    System.out.print(graph.getEdge(i, j) + " ");
                System.out.println();
            }
 
        }
        catch (Exception E) 
        {
            System.out.println("Somthing went wrong");
        }
 
        sc.close();
    }
}

Uruchamianie kodu: Zapisz plik i skompiluj za pomocą javac Represent_Graph_Adjacency_Matrix.java

Przykład:

$ java Represent_Graph_Adjacency_Matrix
Enter the number of vertices:
4
Enter the number of edges:
6
Enter the edges: <to> <from>
1 1
3 4
2 3
1 4
2 4
1 2
The adjacency matrix for the given graph is:
  1 2 3 4
1 1 1 0 1
2 0 0 1 1
3 0 0 0 1
4 0 0 0 0

Przechowywanie wykresów (lista adiakencji)

Lista adiacyencji to zbiór nieuporządkowanych list używanych do reprezentowania skończonego wykresu. Każda lista opisuje zestaw sąsiadów wierzchołka na wykresie. Przechowywanie wykresów zajmuje mniej pamięci.

Zobaczmy wykres i jego macierz przylegania:

Teraz tworzymy listę przy użyciu tych wartości.

Nazywa się to listą przylegania. Pokazuje, które węzły są podłączone do których węzłów. Możemy przechowywać te informacje za pomocą tablicy 2D. Ale będzie nas to kosztować taką samą pamięć jak Matryca Adiakencji. Zamiast tego będziemy używać dynamicznie alokowanej pamięci do przechowywania tej.

Wiele języków obsługuje wektor lub listę, których możemy użyć do przechowywania listy sąsiedztwa. W tym przypadku nie musimy określać rozmiaru listy . Musimy jedynie określić maksymalną liczbę węzłów.

Pseudo-kod będzie:

Procedure Adjacency-List(maxN, E):       // maxN denotes the maximum number of nodes
edge[maxN] = Vector()                    // E denotes the number of edges
for i from 1 to E
    input -> x, y                        // Here x, y denotes there is an edge between x, y
    edge[x].push(y)
    edge[y].push(x)
end for
Return edge

Ponieważ jest to wykres bezkierunkowy, istnieje krawędź od x do y , istnieje również krawędź od y do x . Gdyby to był ukierunkowany wykres, pominęlibyśmy drugi. W przypadku wykresów ważonych musimy również przechowywać koszt. Utworzymy kolejny wektor lub listę o nazwie cost [], aby je przechowywać. Pseudo-kod:

Procedure Adjacency-List(maxN, E):
edge[maxN] = Vector()
cost[maxN] = Vector()
for i from 1 to E
    input -> x, y, w
    edge[x].push(y)
    cost[x].push(w)
end for
Return edge, cost

Na podstawie tego możemy łatwo sprawdzić całkowitą liczbę węzłów podłączonych do dowolnego węzła i czym są te węzły. Zajmuje to mniej czasu niż matryca adiakencji. Ale gdybyśmy musieli dowiedzieć się, czy istnieje różnica między u i v , byłoby łatwiej, gdybyśmy zachowali macierz przylegania.