algorithm
diagram

Invoering

Opmerkingen

Topologische sortering

Een topologische ordening, of een topologische sortering, ordent de hoekpunten in een gerichte acyclische grafiek op een lijn, dwz in een lijst, zodat alle gerichte randen van links naar rechts gaan. Een dergelijke ordening kan niet bestaan als de grafiek een gerichte cyclus bevat, omdat er geen manier is om rechtdoor te gaan op een lijn en toch terug te gaan naar waar u bent begonnen.

Formeel, in een grafiek G = (V, E) , is een lineaire ordening van alle hoekpunten dusdanig dat als G een rand (u, v) ∈ E van hoekpunt u naar hoekpunt v , u in de volgorde aan v voorafgaat.

Het is belangrijk op te merken dat elke DAG ten minste één topologische soort heeft.

Er zijn bekende algoritmen voor het construeren van een topologische ordening van elke DAG in lineaire tijd, een voorbeeld is:

1. Roep depth_first_search(G) aan om de eindtijd vf te berekenen voor elk hoekpunt v
2. Wanneer elk hoekpunt is voltooid, plaatst u dit aan de voorkant van een gekoppelde lijst
3. de gekoppelde lijst met hoekpunten, zoals deze nu is gesorteerd.

Een topologische sortering kan worden uitgevoerd in ϴ(V + E) tijd, omdat het diepte-eerste zoekalgoritme ϴ(V + E) tijd kost en het Ω(1) (constante tijd) kost om elk van |V| hoekpunten vooraan in een gekoppelde lijst.

Veel toepassingen gebruiken gerichte acyclische grafieken om voorrang te geven aan gebeurtenissen. We maken gebruik van topologische sortering zodat we een opdracht krijgen om elk hoekpunt vóór een van de opvolgers te verwerken.

Hoekpunten in een grafiek kunnen taken vertegenwoordigen die moeten worden uitgevoerd en de randen kunnen beperkingen vertegenwoordigen die de ene taak vóór de andere moet uitvoeren; een topologische ordening is een geldige volgorde voor het uitvoeren van de takenreeks taken beschreven in V

Probleeminstantie en zijn oplossing

Laat een vertice v een Task(hours_to_complete: int) , dwz Task(4) beschrijft een Task die 4 uur in beslag neemt en een rand e beschrijft een Cooldown(hours: int) zodat Cooldown(3) een duur van beschrijft tijd om af te koelen na een voltooide taak.

Laat onze grafiek dag heten (omdat het een gerichte acyclische grafiek is) en laat deze 5 hoekpunten bevatten:

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));

waar we de hoekpunten verbinden met gerichte randen zodat de grafiek acyclisch is,

// 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));

dan zijn er drie mogelijke topologische ordeningen tussen A en E ,

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

Thorup's algoritme

Thorup's algoritme voor het kortste pad van één bron voor niet-gerichte grafiek heeft de tijdcomplexiteit O (m), lager dan Dijkstra.

Basisideeën zijn de volgende. (Sorry, ik heb het nog niet geprobeerd te implementeren, dus ik mis misschien een paar kleine details. En het originele papier is betaald, dus ik probeerde het te reconstrueren uit andere bronnen waarnaar het verwijst. Verwijder deze opmerking als je het kunt verifiëren.)

• Er zijn manieren om de overspannende boom in O (m) te vinden (hier niet beschreven). Je moet de overspannende boom "laten groeien" van de kortste rand tot de langste, en het zou een bos zijn met verschillende verbonden componenten voordat het volledig volgroeid is.
• Selecteer een geheel getal b (b> = 2) en bekijk alleen de overspannende bossen met lengtegrens b ^ k. Voeg de componenten samen die exact hetzelfde zijn, maar met verschillende k, en noem de minimale k het niveau van de component. Maak vervolgens logisch componenten in een boom. u is de ouder van v iff u is de kleinste component die verschilt van v die volledig v bevat. De wortel is de hele grafiek en de bladeren zijn enkele hoekpunten in de oorspronkelijke grafiek (met het niveau van negatieve oneindigheid). De boom heeft nog steeds alleen O (n) knooppunten.
• Houd de afstand van elke component tot de bron aan (zoals in het algoritme van Dijkstra). De afstand van een component met meer dan één hoekpunten is de minimale afstand van zijn niet-uitgezette kinderen. Stel de afstand van het bronpunt in op 0 en werk de voorouders dienovereenkomstig bij.
• Overweeg de afstanden in basis b. Wanneer je de eerste keer een knoop in niveau k bezoekt, zet je zijn kinderen in emmers die worden gedeeld door alle knooppunten van niveau k (zoals in bucket-soort, waarbij de heap in het algoritme van Dijkstra wordt vervangen) door het cijfer k en hoger van zijn afstand. Telkens wanneer u een knooppunt bezoekt, overweeg dan alleen de eerste b-emmers, bezoek en verwijder elk van hen, werk de afstand van het huidige knooppunt bij en koppel het huidige knooppunt opnieuw aan zijn eigen ouder met behulp van de nieuwe afstand en wacht op het volgende bezoek voor het volgende emmers.
• Wanneer een blad wordt bezocht, is de huidige afstand de laatste afstand van het hoekpunt. Vouw alle randen ervan in de originele grafiek uit en werk de afstanden dienovereenkomstig bij.
• Bezoek de root-knoop (hele grafiek) herhaaldelijk totdat de bestemming is bereikt.

Het is gebaseerd op het feit dat er geen rand met een lengte van minder dan l tussen twee verbonden componenten van het overspannende bos met lengtebeperking l is, dus vanaf afstand x kon je je alleen op één verbonden component concentreren totdat je de afstand x + l. Je bezoekt enkele hoekpunten voordat hoekpunten met een kortere afstand allemaal worden bezocht, maar dat maakt niet uit omdat het bekend is dat er vanaf deze hoekpunten geen korter pad naar hier zal zijn. Andere delen werken zoals de bucket sort / MSD radix sort, en natuurlijk vereist het de O (m) overspannende boom.

Een cyclus in een gerichte grafiek detecteren met behulp van Depth First Traversal

Een cyclus in een gerichte grafiek bestaat als er een achterrand wordt ontdekt tijdens een DFS. Een achterrand is een rand van een knooppunt naar zichzelf of een van de voorouders in een DFS-structuur. Voor een losgekoppelde grafiek krijgen we een DFS-forest, dus je moet alle vertices in de grafiek doorlopen om onsamenhangende DFS-bomen te vinden.

C ++ implementatie:

    #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;
    }

Resultaat: Zoals hieronder weergegeven, zijn er drie achterranden in de grafiek. Een tussen hoek 0 en 2; tussen hoek 0, 1 en 2; en hoekpunt 3. Tijdcomplexiteit van zoeken is O (V + E) waarbij V het aantal hoekpunten is en E het aantal randen is.

Inleiding tot grafiektheorie

Grafentheorie is de studie van grafieken, die wiskundige structuren zijn die worden gebruikt om paarsgewijze relaties tussen objecten te modelleren.

Wist je dat bijna alle problemen van de planeet Aarde kunnen worden omgezet in problemen van Wegen en Steden en opgelost? Grafentheorie werd vele jaren geleden uitgevonden, zelfs vóór de uitvinding van de computer. Leonhard Euler schreef een paper over de Seven Bridges of Königsberg die wordt beschouwd als de eerste paper van Graph Theory. Sindsdien zijn mensen zich gaan realiseren dat als we een probleem kunnen omzetten in dit City-Road-probleem, we het gemakkelijk kunnen oplossen met behulp van Graph Theory.

Grafentheorie kent vele toepassingen. Een van de meest voorkomende toepassingen is het vinden van de kortste afstand tussen de ene stad en de andere. We weten allemaal dat deze webpagina, om uw pc te bereiken, veel routers van de server moest afleggen. Graph Theory helpt het om de routers te vinden die moesten worden gekruist. Tijdens de oorlog, welke straat moet worden gebombardeerd om de hoofdstad van anderen te ontkoppelen, kan ook dat worden ontdekt met behulp van Graph Theory.

Laten we eerst enkele basisdefinities leren over de grafiektheorie.

grafiek:

Laten we zeggen dat we 6 steden hebben. We markeren ze als 1, 2, 3, 4, 5, 6. Nu verbinden we de steden met wegen tussen elkaar.

Dit is een eenvoudige grafiek waarin sommige steden worden weergegeven met de wegen die hen verbinden. In Grafentheorie noemen we elk van deze steden Node of Vertex en de wegen worden Edge genoemd. Grafiek is gewoon een verbinding van deze knooppunten en randen.

Een knooppunt kan veel dingen vertegenwoordigen. In sommige grafieken vertegenwoordigen knooppunten steden, sommige luchthavens, sommige vertegenwoordigen een vierkant in een schaakbord. Edge vertegenwoordigt de relatie tussen elke knooppunten. Die relatie kan de tijd zijn om van het ene vliegveld naar het andere te gaan, de bewegingen van een ridder van het ene vierkant naar alle andere vierkanten enz.

Pad van ridder in een schaakbord

In eenvoudige woorden, een Node vertegenwoordigt elk object en Edge vertegenwoordigt de relatie tussen twee objecten.

Aangrenzende knoop:

Als een knoop A een rand deelt met knoop B , dan wordt B beschouwd als aangrenzend aan A. Met andere woorden, als twee knooppunten direct verbonden zijn, worden ze aangrenzende knooppunten genoemd. Een knooppunt kan meerdere aangrenzende knooppunten hebben.

Gerichte en niet-geleide grafiek:

De gerichte grafieken, de randen bewegwijzering enerzijds dat middelen de randen unidirectioneel. Aan de andere kant hebben de randen van niet-gerichte grafieken richtingstekens aan beide zijden, wat betekent dat ze bidirectioneel zijn . Gewoonlijk worden niet-gerichte grafieken weergegeven zonder tekens aan weerszijden van de randen.

Laten we aannemen dat er een feest aan de gang is. De mensen in de partij worden vertegenwoordigd door knooppunten en er is een rand tussen twee mensen als ze elkaar een hand geven. Dan is deze grafiek ongericht omdat elke persoon A handen met persoon B schudt en alleen als B ook handen met A schudt. Als daarentegen de randen van iemand een andere persoon B overeenkomt met A's bewonderen B, dan is deze grafiek is gericht, omdat bewondering niet noodzakelijkerwijs beantwoord. Het eerste type grafiek wordt een niet-gerichte grafiek genoemd en de randen worden niet-gerichte randen genoemd, terwijl het laatste type grafiek een gerichte grafiek wordt genoemd en de randen gerichte randen worden genoemd .

Gewogen en ongewogen grafiek:

Een gewogen grafiek is een grafiek waarin een getal (het gewicht) wordt toegewezen aan elke rand. Dergelijke gewichten kunnen bijvoorbeeld kosten, lengtes of capaciteiten vertegenwoordigen, afhankelijk van het probleem bij de hand.

Een ongewogen grafiek is gewoon het tegenovergestelde. We nemen aan dat het gewicht van alle randen hetzelfde is (vermoedelijk 1).

Pad:

Een pad vertegenwoordigt een manier om van het ene knooppunt naar het andere te gaan. Het bestaat uit een reeks randen. Er kunnen meerdere paden tussen twee knooppunten zijn.

In het bovenstaande voorbeeld zijn er twee paden van A naar D. A-> B, B-> C, C-> D is één pad. De kosten van dit pad zijn 3 + 4 + 2 = 9 . Nogmaals, er is een ander pad A-> D. De kosten van dit pad zijn 10 . Het pad dat het laagste kost, wordt het kortste pad genoemd .

Mate:

De graad van een hoekpunt is het aantal randen dat ermee is verbonden. Als er een rand is die verbinding maakt met het hoekpunt aan beide uiteinden (een lus), wordt dit twee keer geteld.

In gerichte grafieken hebben de knooppunten twee soorten graden:

• In graden: het aantal randen dat naar het knooppunt wijst.
• Out-degree: het aantal randen dat van het knooppunt naar andere knooppunten wijst.

Voor niet-gerichte grafieken worden deze eenvoudig graden genoemd.

Sommige algoritmen gerelateerd aan grafiektheorie

• Bellman – Ford algoritme
• Dijkstra's algoritme
• Ford – Fulkerson-algoritme
• Kruskal's algoritme
• Dichtstbijzijnde buur algoritme
• Prim's algoritme
• Diepte-eerste zoekopdracht
• Breedte-eerste zoekopdracht

Grafieken opslaan (Adjacency Matrix)

Om een grafiek op te slaan, zijn er twee methoden:

• Nabijheid Matrix
• Nabijheid lijst

Een aangrenzende matrix is een vierkante matrix die wordt gebruikt om een eindige grafiek weer te geven. De elementen van de matrix geven aan of paren vertices aan elkaar grenzen of niet in de grafiek.

Aangrenzend betekent 'naast of aangrenzend aan iets anders' of naast iets zijn. Uw buren grenzen bijvoorbeeld aan u. In de grafentheorie kunnen we zeggen dat knooppunt B grenst aan knooppunt A als we vanuit knooppunt A naar knoop B kunnen gaan. Nu zullen we leren over het opslaan van welke knooppunten aangrenzend aan welke via Adjacency Matrix. Dit betekent dat we zullen representeren welke knooppunten de rand delen. Matrix betekent hier 2D-array.

Hier ziet u een tabel naast de grafiek, dit is onze aangrenzende matrix. Matrix [i] [j] = 1 geeft hier aan dat er een rand is tussen i en j . Als er geen rand is, zetten we eenvoudig Matrix [i] [j] = 0 .

Deze randen kunnen worden gewogen, alsof het de afstand tussen twee steden kan weergeven. Vervolgens plaatsen we de waarde in Matrix [i] [j] in plaats van 1.

De hierboven beschreven grafiek is bidirectioneel of niet- gericht , wat betekent dat als we vanuit knooppunt 2 naar knooppunt 1 kunnen gaan, we ook vanuit knooppunt 1 naar knooppunt 2 kunnen gaan. Als de grafiek was gericht , zou er aan één kant van de grafiek een pijlteken zijn geweest. Zelfs dan zouden we het kunnen weergeven met behulp van aangrenzende matrix.

We vertegenwoordigen de knooppunten die geen rand delen door oneindig . Een ding dat moet worden opgemerkt, is dat als de grafiek niet-gericht is, de matrix symmetrisch wordt .

De pseudo-code om de matrix te maken:

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

We kunnen de Matrix ook vullen met behulp van deze algemene manier:

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

Voor gerichte grafieken kunnen we Matrix [n2] [n1] = kostenregel verwijderen .

De nadelen van het gebruik van Adjacency Matrix:

Geheugen is een enorm probleem. Hoeveel randen er ook zijn, we hebben altijd een matrix met N * N-formaat nodig waarbij N het aantal knooppunten is. Als er 10000 knooppunten zijn, is de matrixgrootte 4 * 10000 * 10000 rond 381 megabytes. Dit is een enorme verspilling van geheugen als we kijken naar grafieken met een paar randen.

Stel dat we willen weten naar welk knooppunt we vanuit een knooppunt u kunnen gaan. We moeten de hele rij van u controleren , wat veel tijd kost.

Het enige voordeel is dat we de verbinding tussen uv- knooppunten en hun kosten gemakkelijk kunnen vinden met behulp van Adjacency Matrix.

Java-code geïmplementeerd met behulp van bovenstaande pseudo-code:

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();
    }
}

De code uitvoeren: sla het bestand op en compileer met javac Represent_Graph_Adjacency_Matrix.java

Voorbeeld:

$ 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

Grafieken opslaan (Adjacency List)

Adjacency list is een verzameling ongeordende lijsten die worden gebruikt om een eindige grafiek weer te geven. Elke lijst beschrijft de set buren van een hoekpunt in een grafiek. Er is minder geheugen nodig om grafieken op te slaan.

Laten we een grafiek en de bijbehorende matrix bekijken:

Nu maken we een lijst met deze waarden.

Dit wordt aangrenzende lijst genoemd. Het laat zien welke knooppunten zijn verbonden met welke knooppunten. We kunnen deze informatie opslaan met behulp van een 2D-array. Maar kost ons hetzelfde geheugen als Adjacency Matrix. In plaats daarvan gaan we dynamisch toegewezen geheugen gebruiken om dit op te slaan.

Veel talen ondersteunen Vector of Lijst die we kunnen gebruiken om de lijst met adressen op te slaan. Hiervoor hoeven we de grootte van de lijst niet op te geven. We hoeven alleen het maximale aantal knooppunten op te geven.

De pseudo-code zal zijn:

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

Aangezien deze een niet-gerichte grafiek is, is er een rand van x naar y , er is ook een rand van y naar x . Als het een gerichte grafiek was, zouden we de tweede weglaten. Voor gewogen grafieken moeten we ook de kosten opslaan. We zullen een andere vector of lijst met de naam kosten [] maken om deze op te slaan. De pseudo-code:

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

Van deze kunnen we eenvoudig het totale aantal knooppunten vinden dat met een knooppunt is verbonden, en wat deze knooppunten zijn. Het kost minder tijd dan Adjacency Matrix. Maar als we erachter moesten komen of er een rand is tussen u en v , zou het eenvoudiger zijn geweest als we een aangrenzende matrix hielden.