algorithm
Graf

Introduktion

Anmärkningar

Topologisk sortering

En topologisk ordning, eller en topologisk sortering, ordnar vertikalerna i en riktad acyklisk graf på en linje, dvs i en lista, så att alla riktade kanter går från vänster till höger. En sådan beställning kan inte existera om diagrammet innehåller en riktad cykel eftersom det inte finns något sätt att du kan fortsätta rakt på en linje och ändå återvända tillbaka till där du började.

Formellt, i en graf G = (V, E) , då är en linjär ordning av alla dess vertikaler sådan att om G innehåller en kant (u, v) ∈ E från toppunkt u till toppunkt v så går u före v i ordningen.

Det är viktigt att notera att varje DAG har minst en topologisk sortering.

Det finns kända algoritmer för att konstruera en topologisk ordning av vilken DAG som helst i linjär tid, ett exempel är:

1. Ring depth_first_search(G) att beräkna efterbehandlingstider vf för varje toppunkt v
2. När varje toppunkt är klart, sätt in det i framsidan av en länkad lista
3. den länkade listan med vertikaler, eftersom den nu sorteras.

En topologisk sortering kan utföras i ϴ(V + E) -tid, eftersom den första djup-sökalgoritmen tar ϴ(V + E) -tid och det tar Ω(1) (konstant tid) att infoga var och en av |V| vertikaler i framsidan av en länkad lista.

Många applikationer använder riktade acykliska grafer för att indikera föregångar bland händelser. Vi använder topologisk sortering så att vi får en beställning att bearbeta varje toppunkt innan någon av dess efterträdare.

Vertikaler i en graf kan representera uppgifter som ska utföras och kanterna kan representera begränsningar att en uppgift måste utföras före en annan; en topologisk beställning är en giltig sekvens för att utföra de uppsättningar uppgifter som beskrivs i V

Probleminstans och dess lösning

Låt en vertice v beskriva en Task(hours_to_complete: int) , dvs. Task(4) beskriver en Task som tar 4 timmar att slutföra, och en kant e beskriver en Cooldown(hours: int) så att Cooldown(3) beskriver en varaktighet av tid att svalna efter en färdig uppgift.

Låt vår graf kallas dag (eftersom det är en riktad acyklisk graf), och låt den innehålla 5 vertikaler:

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

där vi kopplar samman topparna med riktade kanter så att diagrammet är acykliskt,

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

då finns det tre möjliga topologiska beställningar mellan A och E ,

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

Thorups algoritm

Thorups algoritm för kortaste sökvägen för en källa för den inställda grafen har tidskomplexiteten O (m), lägre än Dijkstra.

Grundläggande idéer är följande. (Tyvärr försökte jag inte implementera det ännu, så jag kanske missar några mindre detaljer. Och originalpapperet är betalvägg så jag försökte rekonstruera det från andra källor som refererar till det. Ta bort den här kommentaren om du kunde verifiera.)

• Det finns sätt att hitta det spännande trädet i O (m) (inte beskrivet här). Du måste "odla" det spännande trädet från den kortaste kanten till det längsta, och det skulle vara en skog med flera anslutna komponenter innan den är fullvuxen.
• Välj ett heltal b (b> = 2) och tänk bara på de spännande skogarna med längdgränsen b ^ k. Slå samman de komponenter som är exakt desamma men med olika k och anropa minsta k för komponentens nivå. Gör sedan logiskt komponenter till ett träd. u är föräldern till v iff u är den minsta komponenten som skiljer sig från v som helt innehåller v. Roten är hela diagrammet och bladen är enstaka vertikaler i den ursprungliga grafen (med nivån av negativ oändlighet). Trädet har fortfarande bara O (n) noder.
• Behåll avståndet för varje komponent till källan (som i Dijkstra's algoritm). Avståndet för en komponent med mer än en vertik är det minsta avståndet för dess expanderade barn. Ställ in avståndet från källkoden till 0 och uppdatera förfäderna i enlighet därmed.
• Tänk på avståndet i bas b. När du besöker en nod i nivå k första gången lägger du sina barn i hinkar som delas av alla noder i nivå k (som i hinksortering, ersätter högen i Dijkstra's algoritm) med siffran k och högre av dess avstånd. Varje gång du besöker en nod överväger bara de första b-skoporna, besöker och tar bort var och en av dem, uppdaterar avståndet för den aktuella noden och kopplar om den aktuella noden till sin egen förälder med det nya avståndet och väntar på nästa besök för följande hinkar.
• När ett blad besöks, är det aktuella avståndet det slutliga avståndet till toppunktet. Expandera alla kanter från det i den ursprungliga grafen och uppdatera avståndet i enlighet därmed.
• Besök rotnoden (hela diagrammet) upprepade gånger tills destinationen nås.

Det är baserat på det faktum att det inte finns en kant med längd mindre än l mellan två anslutna komponenter i den spännande skogen med längdbegränsning l, så från början på avstånd x kan du bara fokusera på en ansluten komponent tills du når avståndet x + l. Du kommer att besöka vissa topppunkter innan topppunkter med kortare avstånd alla besöks, men det spelar ingen roll eftersom det är känt att det inte kommer att finnas en kortare väg till här från dessa toppningar. Andra delar fungerar som hinkens sortering / MSD radix-sortering, och naturligtvis krävs det O (m) -trädet.

Detektera en cykel i en riktad graf med hjälp av Depth First Traversal

En cykel i en riktad graf finns om det finns en bakkant upptäckt under en DFS. En bakkant är en kant från en nod till sig själv eller en av förfäderna i ett DFS-träd. För en frånkopplad graf får vi en DFS-skog, så du måste iterera igenom alla hörn i diagrammet för att hitta osammanhängande DFS-träd.

C ++ implementering:

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

Resultat: Som visas nedan finns det tre bakkantar i diagrammet. En mellan topp 0 och 2; mellan vertikalen 0, 1 och 2; och topp 3. Tidskomplexiteten för sökningen är O (V + E) där V är antalet vertikaler och E är antalet kanter.

Introduktion till grafteori

Grafteori är studiet av grafer, som är matematiska strukturer som används för att modellera parvisa förhållanden mellan objekt.

Visste du att nästan alla jordens problem kan omvandlas till problem med vägar och städer och lösas? Grafteori uppfanns för många år sedan, redan före datorns uppfinning. Leonhard Euler skrev ett papper om de sju broarna i Königsberg som betraktas som den första uppsatsen i grafteori. Sedan dess har människor insett att om vi kan konvertera något problem till detta City-Road-problem, kan vi enkelt lösa det genom grafteori.

Grafteori har många applikationer. En av de vanligaste applikationerna är att hitta det kortaste avståndet mellan en stad till en annan. Vi vet alla att för att nå din dator måste denna webbsida resa många routrar från servern. Grafteori hjälper den att ta reda på routrarna som behövde korsas. Under krig, vilken gata som måste bombarderas för att koppla bort huvudstaden från andra, kan man också få reda på det med Grafteori.

Låt oss först lära oss några grundläggande definitioner på grafteori.

Graf:

Låt oss säga att vi har 6 städer. Vi markerar dem som 1, 2, 3, 4, 5, 6. Nu förbinder vi städerna som har vägar mellan varandra.

Detta är en enkel graf där vissa städer visas med vägar som förbinder dem. I grafteori kallar vi var och en av dessa städer Node eller Vertex och vägarna kallas Edge. Graf är helt enkelt en anslutning av dessa noder och kanter.

En nod kan representera många saker. I vissa grafer representerar noder städer, vissa representerar flygplatser, andra representerar en kvadrat i ett schackbräde. Edge representerar förhållandet mellan varje nod. Det förhållandet kan vara tiden att gå från en flygplats till en annan, rörelserna från en riddare från en kvadrat till alla andra rutor etc.

Riddares väg i ett schackbräde

I enkla ord representerar en nod varje objekt och Edge representerar förhållandet mellan två objekt.

Intilliggande nod:

Om en nod A delar en kant med nod B , anses B vara intill A. Med andra ord, om två noder är direkt anslutna, kallas de intilliggande noder. En nod kan ha flera angränsande noder.

Riktad och odirigerad graf:

I riktade grafer har kanterna riktningsskyltar på ena sidan, vilket betyder att kanterna är riktade i en riktning . Å andra sidan har kanterna på riktade grafer riktningsskyltar på båda sidor, det betyder att de är dubbelriktade . Vanligtvis är inte riktade grafer representerade utan tecken på båda sidor om kanterna.

Låt oss anta att det är ett parti på gång. Folket i partiet representeras av noder och det finns en kant mellan två personer om de skakar hand. Då är denna graf inte riktad eftersom varje person A skakar hand med person B om och bara om B också skakar hand med A. Däremot, om kanterna från en person A till en annan person B motsvarar A : s beundra B , riktas denna graf, eftersom beundran inte nödvändigtvis återupprepas. Den tidigare typen av graf kallas en riktad kurva och kanterna kallas riktade kanter medan den senare typen av graf kallas en riktad graf och kanterna kallas riktade kanter.

Viktad och ovägd graf:

Ett viktat diagram är ett diagram där ett nummer (vikten) tilldelas varje kant. Sådana vikter kan representera till exempel kostnader, längder eller kapacitet, beroende på problemet.

En ovägd graf är helt enkelt motsatsen. Vi antar att vikten på alla kanter är densamma (förmodligen 1).

Väg:

En sökväg representerar ett sätt att gå från en nod till en annan. Den består av kantsekvensen. Det kan finnas flera vägar mellan två noder.

I exemplet ovan finns det två vägar från A till D. A-> B, B-> C, C-> D är en väg. Kostnaden för denna väg är 3 + 4 + 2 = 9 . Återigen finns det en annan väg A-> D. Kostnaden för denna väg är 10 . Den väg som kostar den lägsta kallas kortaste väg .

Grad:

Graden av ett toppunkt är antalet kanter som är anslutna till det. Om det finns någon kant som ansluter till topppunkten i båda ändarna (en slinga) räknas två gånger.

I riktade diagram har noderna två typer av grader:

• Graden: Antalet kanter som pekar på noden.
• Utgradering: Antalet kanter som pekar från noden till andra noder.

För riktade grafer kallas de helt enkelt grad.

Vissa algoritmer relaterade till grafteori

• Bellman – Ford algoritm
• Dijkstra's algoritm
• Ford – Fulkerson algoritm
• Kruskals algoritm
• Närmaste grannalgoritm
• Prims algoritm
• Djup-första sökning
• Utöka första sökningen

Lagra diagram (Adjacency Matrix)

För att lagra en graf är två metoder vanliga:

• Adjacency matris
• Adjacency List

En anpassningsmatris är en kvadratmatris som används för att representera en ändlig graf. Elementen i matrisen indikerar om par av vertikaler är intill eller inte i grafen.

Angränsande betyder "bredvid eller angränsar till något annat" eller att vara bredvid något. Till exempel är dina grannar intill dig. I grafteori, om vi kan gå till nod B från nod A , kan vi säga att nod B ligger intill nod A. Nu kommer vi att lära dig hur du lagrar vilka noder som gränsar till vilka via Adjacency Matrix. Det betyder att vi kommer att representera vilka noder som delar kanten mellan dem. Här betyder matris 2D-array.

Här kan du se en tabell bredvid diagrammet, detta är vår adjacensmatris. Här representerar Matrix [i] [j] = 1 det finns en kant mellan i och j . Om det inte finns någon kant lägger vi helt enkelt Matrix [i] [j] = 0 .

Dessa kanter kan vägas, liksom det kan representera avståndet mellan två städer. Sedan lägger vi värdet i Matrix [i] [j] istället för att sätta 1.

Grafen som beskrivs ovan är Bidirectional or Undirected , det betyder att om vi kan gå till nod 1 från nod 2 kan vi också gå till nod 2 från nod 1 . Om grafen var riktad , skulle det ha funnits piltecken på ena sidan av grafen. Även då kan vi representera det med hjälp av anpassningsmatris.

Vi representerar de noder som inte delar fördel av oändligheten . En sak att lägga märke till är att om grafen inte är riktad blir matrisen symmetrisk .

Pseudokoden för att skapa matrisen:

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

Vi kan också fylla matrisen på detta vanliga sätt:

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

För riktade diagram kan vi ta bort Matrix [n2] [n1] = kostnadsraden .

Nackdelarna med att använda Adjacency Matrix:

Minne är ett enormt problem. Oavsett hur många kanter det finns kommer vi alltid att behöva matris i N * N-storlek där N är antalet noder. Om det finns 10000 noder är matrisstorleken 4 * 10000 * 10000 cirka 381 megabyte. Detta är ett enormt slöseri med minnet om vi tar hänsyn till diagram som har några kanter.

Anta att vi vill ta reda på vilken nod vi kan gå från en nod u . Vi måste kontrollera hela raden med u , vilket kostar mycket tid.

Den enda fördelen är att vi enkelt kan hitta kopplingen mellan uv- noder och deras kostnader med hjälp av Adjacency Matrix.

Java-kod implementerad med ovanstående pseudokod:

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

Köra koden: Spara filen och kompilera med javac Represent_Graph_Adjacency_Matrix.java

Exempel:

$ 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

Lagra diagram (Adjacency List)

Adjacency-lista är en samling av oordnade listor som används för att representera en ändlig graf. Varje lista beskriver uppsättningen grannar i ett toppunkt i en graf. Det tar mindre minne att lagra grafer.

Låt oss se en graf och dess angränsande matris:

Nu skapar vi en lista med dessa värden.

Detta kallas adjacency-lista. Den visar vilka noder som är anslutna till vilka noder. Vi kan lagra denna information med en 2D-grupp. Men kommer att kosta oss samma minne som Adjacency Matrix. Istället kommer vi att använda dynamiskt tilldelat minne för att lagra det här.

Många språk stöder vektor eller lista som vi kan använda för att lagra adjacency-lista. För dessa behöver vi inte ange storleken på listan . Vi behöver bara ange det maximala antalet noder.

Pseudokoden kommer att vara:

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

Eftersom den här är en riktad graf, det finns en kant från x till y , det finns också en kant från y till x . Om det var en riktad graf, skulle vi utelämna den andra. För viktade grafer måste vi också spara kostnaderna. Vi skapar en annan vektor eller lista med namnet kostnad [] för att lagra dessa. Pseudokoden:

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

Från den här kan vi enkelt ta reda på det totala antalet noder som är anslutna till vilken nod som helst, och vad dessa noder är. Det tar mindre tid än Adjacency Matrix. Men om vi behövde ta reda på om det finns en kant mellan u och v , hade det varit lättare om vi hade en adjacensmatris.