algorithm
Grafico

introduzione

Osservazioni

Ordinamento topologico

Un ordinamento topologico, o un ordinamento topologico, ordina i vertici in un grafo aciclico diretto su una linea, cioè in una lista, in modo che tutti i bordi diretti vadano da sinistra a destra. Un tale ordinamento non può esistere se il grafico contiene un ciclo diretto perché non c'è modo di continuare a andare dritto su una linea e tornare al punto da cui si è partiti.

Formalmente, in un grafo G = (V, E) , quindi un ordinamento lineare di tutti i suoi vertici è tale che se G contiene un bordo (u, v) ∈ E dal vertice u al vertice v poi u precede v nell'ordinamento.

È importante notare che ogni DAG ha almeno un ordinamento topologico.

Esistono algoritmi noti per la costruzione di un ordinamento topologico di qualsiasi DAG in tempo lineare, un esempio è:

1. Chiama depth_first_search(G) per calcolare i tempi di finitura vf per ogni vertice v
2. Al termine di ogni vertice, inserirlo nella parte anteriore di un elenco collegato
3. l'elenco collegato di vertici, come è ora ordinato.

Un ordinamento topologico può essere eseguito nel tempo ϴ(V + E) , poiché l'algoritmo di ricerca in profondità richiede il tempo ϴ(V + E) e impiega Ω(1) (tempo costante) per inserire ciascuno di |V| vertici nella parte anteriore di un elenco collegato.

Molte applicazioni utilizzano grafici aciclici diretti per indicare le precedenze tra gli eventi. Usiamo l'ordinamento topologico in modo da ottenere un ordine per elaborare ogni vertice prima di uno qualsiasi dei suoi successori.

Vertici in un grafico possono rappresentare compiti da eseguire e i bordi possono rappresentare vincoli che un compito deve essere eseguito prima di un altro; un ordinamento topologico è una sequenza valida per eseguire l'insieme di compiti descritto in V

Istanza problema e la sua soluzione

Lasciare un vertice v descrivere un Task(hours_to_complete: int) , cioè Task(4) descrive un Task che richiede 4 ore per essere completato, e un bordo e descrive un Cooldown(hours: int) tale che Cooldown(3) descrive una durata di tempo di raffreddarsi dopo un'attività completata.

Lascia che il nostro grafo sia chiamato dag (dato che è un grafo aciclico diretto), e lascia che contenga 5 vertici:

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

dove colleghiamo i vertici con i bordi diretti in modo tale che il grafico sia aciclico,

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

poi ci sono tre ordini topologici possibili tra A ed E ,

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

Algoritmo di Thorup

L'algoritmo di Thorup per il percorso più breve a sorgente singola per il grafo non orientato ha la complessità temporale O (m), inferiore a Dijkstra.

Le idee di base sono le seguenti. (Scusa, non ho ancora provato a implementarlo, quindi potrei perdere alcuni dettagli minori e il documento originale è paywall, quindi ho provato a ricostruirlo da altre fonti a cui fa riferimento. Rimuovi questo commento se puoi verificare.)

• Ci sono modi per trovare lo spanning tree in O (m) (non descritto qui). È necessario "far crescere" lo spanning tree dal lato più corto al più lungo, e sarebbe una foresta con diversi componenti connessi prima che diventasse completamente cresciuta.
• Selezionare un numero intero b (b> = 2) e considerare solo le foreste con spanning con limite di lunghezza b ^ k. Unisci i componenti che sono esattamente uguali ma con k diversi e chiama il k minimo del livello del componente. Quindi crea logicamente i componenti in un albero. u è il genitore di v se è il componente più piccolo distinto da v che contiene pienamente v. La radice è l'intero grafico e le foglie sono singoli vertici nel grafico originale (con il livello di infinito negativo). L'albero ha ancora solo nodi O (n).
• Mantenere la distanza di ogni componente dalla sorgente (come nell'algoritmo di Dijkstra). La distanza di un componente con più di un vertice è la distanza minima dei suoi bambini non espansi. Imposta la distanza del vertice sorgente su 0 e aggiorna gli antenati di conseguenza.
• Considera le distanze in base b. Quando visiti un nodo di livello k la prima volta, metti i suoi figli in bucket condivisi da tutti i nodi di livello k (come in bucket sort, sostituendo l'heap nell'algoritmo di Dijkstra) con la cifra k e più in alto della sua distanza. Ogni volta che si visita un nodo, considerare solo i suoi primi b bucket, visitare e rimuovere ciascuno di essi, aggiornare la distanza del nodo corrente e ricollegare il nodo corrente al proprio genitore utilizzando la nuova distanza e attendere la successiva visita per il seguente secchi.
• Quando una foglia viene visitata, la distanza corrente è la distanza finale del vertice. Espandi tutti i bordi da esso nel grafico originale e aggiorna le distanze di conseguenza.
• Visita il nodo radice (intero grafico) ripetutamente fino a raggiungere la destinazione.

Si basa sul fatto che, non esiste un margine con lunghezza inferiore a 1 tra due componenti connesse della foresta di spanning con limite di lunghezza l, quindi, partendo dalla distanza x, è possibile concentrarsi solo su un componente collegato fino a raggiungere la distanza x + l. Visiterai alcuni vertici prima che tutti i vertici con una distanza più breve vengano tutti visitati, ma non importa perché è noto che non ci sarà un percorso più breve da qui da quei vertici. Altre parti funzionano come la benna sort / MSD radix sort e, naturalmente, richiede l'albero spanning O (m).

Rilevazione di un ciclo in un grafico diretto utilizzando Profondità primo attraversamento

Esiste un ciclo in un grafico diretto se è stato rilevato un bordo posteriore durante un DFS. Un margine posteriore è un limite da un nodo a se stesso o uno degli antenati in un albero DFS. Per un grafico disconnesso, otteniamo una foresta DFS, quindi devi scorrere tutti i vertici nel grafico per trovare alberi DFS disgiunti.

Implementazione del 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;
    }

Risultato: come mostrato di seguito, ci sono tre bordi posteriori nel grafico. Uno tra i vertici 0 e 2; tra vertice 0, 1 e 2; e vertice 3. La complessità temporale della ricerca è O (V + E) dove V è il numero di vertici ed E è il numero di spigoli.

Introduzione alla teoria dei grafi

Teoria dei grafi è lo studio dei grafici, che sono strutture matematiche utilizzate per modellare relazioni a coppie tra oggetti.

Lo sapevi, quasi tutti i problemi del pianeta Terra possono essere convertiti in problemi di strade e città e risolti? La teoria dei grafi fu inventata molti anni fa, ancor prima dell'invenzione del computer. Leonhard Euler ha scritto un articolo sui Seven Bridges of Königsberg che è considerato il primo articolo di Graph Theory. Da allora, le persone hanno capito che se siamo in grado di convertire qualsiasi problema in questo problema City-Road, possiamo risolverlo facilmente con la Teoria dei Grafici.

La teoria dei grafi ha molte applicazioni. Una delle applicazioni più comuni è trovare la distanza più breve tra una città e l'altra. Sappiamo tutti che per raggiungere il PC, questa pagina Web ha dovuto viaggiare su molti router dal server. La teoria dei grafi aiuta a scoprire i router che devono essere superati. Durante la guerra, quale strada ha bisogno di essere bombardata per disconnettere la capitale dagli altri, anche questa può essere trovata usando la teoria dei grafi.

Prima impariamo alcune definizioni di base sulla teoria dei grafi.

Grafico:

Diciamo, abbiamo 6 città. Li contrassegniamo come 1, 2, 3, 4, 5, 6. Ora colleghiamo le città che hanno strade tra loro.

Questo è un semplice grafico in cui vengono mostrate alcune città con le strade che le connettono. Nella teoria dei grafi, chiamiamo ciascuna di queste città nodo o vertice e le strade sono chiamate Edge. Il grafico è semplicemente una connessione di questi nodi e bordi.

Un nodo può rappresentare molte cose. In alcuni grafici, i nodi rappresentano città, alcuni rappresentano aeroporti, altri rappresentano un quadrato in una scacchiera. Edge rappresenta la relazione tra ciascun nodo. Quella relazione può essere il tempo di andare da un aeroporto a un altro, le mosse di un cavaliere da una piazza a tutte le altre piazze ecc.

Sentiero del cavaliere in una scacchiera

In parole semplici, un nodo rappresenta qualsiasi oggetto e Edge rappresenta la relazione tra due oggetti.

Nodo adiacente:

Se un nodo A condivide un fronte con il nodo B , allora B è considerato adiacente ad A. In altre parole, se due nodi sono connessi direttamente, sono chiamati nodi adiacenti. Un nodo può avere più nodi adiacenti.

Grafico diretto e non indiretto:

Nei grafici orientati, i bordi hanno segni di direzione su un lato, il che significa che i bordi sono unidirezionali . D'altra parte, i bordi dei grafici non orientati hanno segni di direzione su entrambi i lati, il che significa che sono bidirezionali . Solitamente i grafici non orientati sono rappresentati senza segni su entrambi i lati dei bordi.

Supponiamo che ci sia una festa in corso. Le persone nel gruppo sono rappresentate dai nodi e c'è un confine tra due persone se si stringono la mano. Quindi questo grafico non è diretto perché ogni persona A stringe la mano alla persona B se e solo se B stringe anche le mani con A. Al contrario, se i bordi da una persona A ad un'altra persona B corrisponde ad A che ammira B , allora questo grafico è diretto, perché l'ammirazione non è necessariamente ricambiata. Il precedente tipo di grafico è chiamato un grafo non orientato e i bordi sono chiamati bordi non diretti mentre l'ultimo tipo di grafico è chiamato grafico diretto ei bordi sono detti bordi diretti.

Grafico ponderato e non ponderato:

Un grafico ponderato è un grafico in cui un numero (il peso) è assegnato a ciascun bordo. Tali pesi potrebbero rappresentare, ad esempio, costi, lunghezze o capacità, a seconda del problema in questione.

Un grafico non ponderato è semplicemente l'opposto. Supponiamo che il peso di tutti i bordi sia lo stesso (presumibilmente 1).

Sentiero:

Un percorso rappresenta un modo per passare da un nodo all'altro. Consiste in una sequenza di bordi. Possono esserci più percorsi tra due nodi.

Nell'esempio sopra, ci sono due percorsi da A a D. A-> B, B-> C, C-> D è un percorso. Il costo di questo percorso è 3 + 4 + 2 = 9 . Di nuovo, c'è un altro percorso A-> D. Il costo di questo percorso è 10 . Il percorso che costa il più basso è chiamato percorso più breve .

Grado:

Il grado di un vertice è il numero di spigoli che sono collegati ad esso. Se c'è uno spigolo che si collega al vertice ad entrambe le estremità (un loop) viene contato due volte.

Nei grafici diretti, i nodi hanno due tipi di gradi:

• In-degree: il numero di spigoli che puntano al nodo.
• Fuori misura: il numero di archi che puntano dal nodo ad altri nodi.

Per i grafi non orientati, vengono semplicemente chiamati gradi.

Alcuni algoritmi relativi alla teoria dei grafi

• Algoritmo di Bellman-Ford
• L'algoritmo di Dijkstra
• Algoritmo Ford-Fulkerson
• L'algoritmo di Kruskal
• Algoritmo del vicino più vicino
• L'algoritmo di Prim
• Ricerca approfondita
• Ricerca per ampiezza

Memorizzazione di grafici (matrice di adiacenza)

Per memorizzare un grafico, sono comuni due metodi:

• Matrice di adiacenza
• Lista di adiacenza

Una matrice di adiacenza è una matrice quadrata usata per rappresentare un grafico finito. Gli elementi della matrice indicano se coppie di vertici sono adiacenti o meno nel grafico.

Adiacente significa "accanto o contiguo a qualcos'altro" o essere accanto a qualcosa. Ad esempio, i tuoi vicini sono adiacenti a te. Nella teoria dei grafi, se possiamo andare al nodo B dal nodo A , possiamo dire che il nodo B è adiacente al nodo A. Ora impareremo come memorizzare quali nodi sono adiacenti a quello tramite Adjacency Matrix. Ciò significa che rappresenteremo quali nodi condividono il confine tra loro. Qui matrice significa array 2D.

Qui puoi vedere una tabella accanto al grafico, questa è la nostra matrice di adiacenza. Qui Matrix [i] [j] = 1 rappresenta un margine tra i e j . Se non c'è margine, semplicemente mettiamo Matrix [i] [j] = 0 .

Questi bordi possono essere ponderati, come può rappresentare la distanza tra due città. Quindi inseriremo il valore in Matrix [i] [j] invece di inserire 1.

Il grafico sopra descritto è Bidirezionale o Indiretto , ciò significa che se possiamo andare al nodo 1 dal nodo 2 , possiamo anche andare al nodo 2 dal nodo 1 . Se il grafico era diretto , allora ci sarebbe stato un segno di freccia su un lato del grafico. Anche allora, potremmo rappresentarlo usando la matrice di adiacenza.

Rappresentiamo i nodi che non condividono il confine con l' infinito . Una cosa da notare è che, se il grafico non è orientato, la matrice diventa simmetrica .

Lo pseudo-codice per creare la matrice:

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

Possiamo anche popolare Matrix usando questo modo comune:

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

Per i grafici diretti, possiamo rimuovere Matrix [n2] [n1] = riga di costo .

Gli svantaggi dell'utilizzo di Adjacency Matrix:

La memoria è un grosso problema. Non importa quanti spigoli ci siano, avremo sempre bisogno della matrice N * N in cui N è il numero di nodi. Se ci sono 10000 nodi, la dimensione della matrice sarà 4 * 10000 * 10000 circa 381 megabyte. Questo è un enorme spreco di memoria se consideriamo i grafici che hanno pochi bordi.

Supponiamo di voler scoprire a quale nodo possiamo andare da un nodo u . Avremo bisogno di controllare l'intera fila di u, che costa un sacco di tempo.

L'unico vantaggio è che possiamo facilmente trovare la connessione tra i nodi uv e il loro costo usando Adjacency Matrix.

Codice Java implementato usando lo pseudo-codice sopra:

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

Esecuzione del codice: salva il file e compila usando javac Represent_Graph_Adjacency_Matrix.java

Esempio:

$ 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

Memorizzazione di grafici (elenco di adiacenze)

L'elenco di adiacenza è una raccolta di liste non ordinate utilizzate per rappresentare un grafico finito. Ogni elenco descrive l'insieme di vicini di un vertice in un grafico. Ci vuole meno memoria per archiviare i grafici.

Vediamo un grafico e la sua matrice di adiacenza:

Ora creiamo una lista usando questi valori.

Questo è chiamato elenco di adiacenza. Mostra quali nodi sono connessi a quali nodi. Possiamo memorizzare queste informazioni usando un array 2D. Ma ci costerà la stessa memoria di Adjacency Matrix. Invece useremo la memoria allocata dinamicamente per immagazzinarla.

Molte lingue supportano Vector o List che possiamo usare per memorizzare l'elenco di adiacenza. Per questi, non è necessario specificare la dimensione della lista . Abbiamo solo bisogno di specificare il numero massimo di nodi.

Lo pseudo-codice sarà:

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

Dato che questo è un grafo non orientato, esiste un bordo da x a y , c'è anche un bordo da y a x . Se fosse un grafico diretto, ometteremmo il secondo. Per i grafici ponderati, dobbiamo anche archiviare il costo. Creeremo un altro vettore o elenco denominato costo [] per memorizzarli. Lo pseudo-codice:

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

Da questo, possiamo facilmente scoprire il numero totale di nodi connessi a qualsiasi nodo e quali sono questi nodi. Richiede meno tempo di Adjacency Matrix. Ma se avessimo bisogno di scoprire se c'è un vantaggio tra u e v , sarebbe stato più semplice mantenere una matrice di adiacenza.