Grafi

Indice

โžก๏ธ Grafo orientato (directed)

รˆ una coppia G=(V,E) dove:

  • V รจ un insieme di nodi (node) o vertici (vertex)
  • E รจ un insieme di coppie ordinate di nodi (u,v) dette archi o lati (edge)

Esempio

Input:

V={a,b,c,d,e,f}
E={(a,b),(a,d),(b,c),(d,a),(d,c),(d,e),(e,c)}

Output:

graph TB
        A((a))
        B((b))
        C((c))
        D((d))
        E((e))
        F((f))
        
        A-->B
        A-->D
        D-->A
        B-->C
        D-->C
        D-->E
        E-->C
        F

โ†”๏ธ Grafo non orientato (undirected)

รˆ una coppia G=(V,E) dove:

  • V รจ un insieme di nodi (node) o vertici (vertex)
  • E รจ un insieme di coppie non ordinate di nodi (u,v) dette archi o lati (edge)

Esempio

Input:

V={a,b,c,d,e,f}
E={(a,b),(a,d),(b,c),(d,a),(d,c),(d,e),(e,c)}

Output:

graph TB
        A((a))
        B((b))
        C((c))
        D((d))
        E((e))
        F((f))

        A---B
        A---D
        D---A
        B---C
        D---C
        D---E
        E---C
        F

โš™๏ธ Proprietร  dei grafi

  • n=|V|: numero di nodi
  • m=|E|: numero di archi

Alcune relazioni fra n e m:

  • in un grafo non orientato, mโ‰คn(nโˆ’1)2=O(n2)
  • in un grafo orientato, mโ‰คn2โˆ’n=O(n2)
  • in un grafo orientato aciclico, il numero massimo di archi che possono essere contenuti senza creare un ciclo รจ โˆ‘0nโˆ’1ย i=n(nโˆ’1)2

Complessitร  di algoritmi su grafi:

  • La complessitร  รจ espressa in termini sia di n che di m (ad es. O(n+m))

โŒจ๏ธ Implementazione

Matrici di adiacenza

Utilizziamo una matrice per implementare il grafo, ogni cella ha la seguente regola:

muv={1(u,v)โˆˆE0(u,v)โˆ‰E

Grafi orientati

Utilizziamo l'intera matrice, lo spazio utilizzato sarร  n2 bit.

Grafi non orientati

Utilizziamo metร  matrice, lo spazio utilizzato sarร  comunque n2 bit, ma quello realmente utilizzato รจ di n(nโˆ’1)2 bit.

Grafi pesati

  • Gli archi possono avere un peso (costo, profitto, etc.)
  • Se non esiste arco fra due vertici, il peso assume un valore che dipende dal problema - e.g. w(u,v)=0 oppure +โˆž
  • Al posto di 1 nella matrice si mette il valore del peso

Liste di adiacenza

Utilizziamo un vettore di liste per implementare il grafo, ogni cella del vettore corrisponde ad un nodo del grafo, che a sua volta contiene la lista di nodi adiacenti. Quindi v[u]=G.adj(u)={vย |ย (u,v)โˆˆE}.

Grafi orientati

Dobbiamo inserire gli archi tra i nodi una solta volta, lo spazio utilizzato sarร  di an+bm bit.

Grafi non orientati

Dobbiamo inserire gli archi tra i nodi due volte, lo spazio utilizzato sarร  di an+2โ‹…bm bit.

Grafi pesati

  • Gli archi possono avere un peso (costo, profitto, etc.)
  • Se non esiste arco fra due vertici, il peso assume un valore che dipende dal problema - e.g. w(u,v)=0 oppure +โˆž
  • Nella lista di nodi adiacenti avremo anche un campo peso in ogni nodo.

Per riassumere

Matrici di adiacenza Liste di adiacenza
Spazio richiesto: O(n2) Spazio richiesto: O(n+m)
Verificare se u รจ adiacente a v richiede tempo O(1) Verificare se u รจ adiacente a v richiede tempo O(n)
Iterare su tutti gli archi richiede tempo O(n2) Iterare su tutti gli archi richiede tempo O(n+m)
Ideale per grafi densi Ideale per grafi sparsi

๐Ÿ”Ž Visita di un grafo

Dato un grafo G=(V,E) e un vertice rโˆˆV (radice, sorgente), visitare una e una volta sola tutti i nodi del grafo che possono essere raggiunti da r.

Visita in profonditร  Depth-First Search (DFS) Visita in ampiezza Breadth First Search (BFS)
Per esplorare un intero grafo, non solo i nodi raggiungibili da una singola sorgente Per esplorare tutti i nodi raggiungibili da una singola sorgente
Per ogni nodo adiacente, si visita ricorsivamente tale nodo, visitando ricorsivamente i suoi nodi adiacenti, etc. Prima si visita la radice, poi i nodi a distanza 1 dalla radice, poi a distanza 2, etc.
Utilizzato per l'ordinamento topologico, componente connesse, componenti fortemente connesse Utilizzato per calcolare i cammini piรน brevi da una singola sorgente

Visita in ampiezza Breadth First Search (BFS)

Obiettivi:

  • Visitare i nodi a distanze crescenti dalla sorgente
  • Calcolare il cammino piรน breve da r a tutti gli altri nodi

Implementazione

Utilizziamo una coda per inserire i nodi che scopriamo ad ogni iterazione. Visto che รจ una coda, quando inseriamo i figli di un nodo, finiscono in fondo alla coda. In questo modo vengono analizzati prima tutti i nodi a distanza k dal nodo di partenza.

void BFS(vector<vector<int>>& graph, int root) {
    queue<int> queue;
    vector<bool> visited(graph.size(), false);
    visited.at(root) = true;
    queue.push(root);
    while(!queue.empty()) {
        int v = queue.front();
	    queue.pop();
	    cout << v << " "; 
        for(int adj : graph.at(v)) {
            if(!visited.at(adj)) {
                visited.at(adj) = true;
                queue.push(adj);
            }
        }
    }
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi[1])
  • Space complexity: O(n)

๐Ÿ”ข Numero di Erdos

Il numero di Erdล‘s รจ un modo per descrivere la "distanza" tra una persona e il matematico ungherese Paul Erdล‘s in termini di collaborazione in pubblicazioni matematiche. รˆ stato creato dagli amici di Erdล‘s come tributo scherzoso all'enorme numero di pubblicazioni da lui scritte in collaborazione con un gran numero di matematici diversi.

Nel nostro caso calcoliamo la distanze tra un nodo e tutti gli altri nodi e li memorizziamo in un array.

vector<int> distance(vector<vector<int>>& graph, int node) {
    vector<int> distance(graph.size(), -1);
    queue<int> queue;
    distance.at(node) = 0;
    queue.push(node);
    while(!queue.empty()) {
        int v = queue.front();
        queue.pop();
        for(int adj : graph.at(v)) {
            if(distance.at(adj) == -1) {
                distance.at(adj) = distance.at(v) + 1;
                queue.push(adj);
            }
        }
    }
    return distance;
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

Cammino tra 2 nodi

Modifichiamo leggermente la funzione precedente e aggiungiamo un vettore per memorizzare il padre di ogni nodo. In questo modo possiamo ottenere direttamente il cammino tra 2 nodi "risalendo" tutti i padri.

vector<int> distance(vector<vector<int>>& graph, int node, vector<int>& parent) {
    vector<int> distance(graph.size(), -1);
    queue<int> queue;
    distance.at(node) = 0;
    parent.at(node) = node;
    queue.push(node);
    while(!queue.empty()) {
        int v = queue.front();
        queue.pop();
        for(int adj : graph.at(v)) {
            if(distance.at(adj) == -1) {
                distance.at(adj) = distance.at(v) + 1;
                parent.at(adj) = v;
                queue.push(adj);
            }
        }
    }
    return distance;
}

void printPathHelper(int from, int to, vector<int>& parent) {
    if(from == to) {
        cout << from << " "; 
        return;
    }
    else if(parent.at(to) == -1) {
        cout << "The node " << to << " is unreachable" << endl; 
        return;
    }
    else {
        printPathHelper(from, parent.at(to), parent);
        cout << to << " ";
    }
}

void printPath(vector<vector<int>>& graph, int from, int to) {
    vector<int> parent(graph.size(), -1);
    distance(graph, from, parent);
    printPathHelper(from, to, parent);
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

Visita in profonditร  Depth-First Search (DFS)

Come detto in precedenza, รจ utilizzata per esplorare un intero grafo, non solo i nodi raggiungibili da una singola sorgente.

Implementazione ricorsiva

void DFS(vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    for(int i = 0; i < graph.size(); i++) {
        if(!visited.at(i))
            DFSHelper(graph, i, visited);
    }
    cout << endl;
}

void DFSHelper(vector<vector<int>>& graph, int root, vector<bool>& visited) {
    visited.at(root) = true;
    cout << root << " ";
    for(int adj : graph.at(root)) {
        if(!visited.at(adj))
            DFSHelper(graph, adj, visited);
    }
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

Tuttavia, eseguire una DFS basata su chiamate ricorsive puรฒ essere rischioso in grafi molto grandi e connessi. รˆ possibile che la profonditร  raggiunta sia troppo grande per la dimensione dello stack del linguaggio. In tali casi, si preferisce utilizzare una BFS oppure una DFS basata su stack esplicito.

Implementazione iterativa

Il concetto รจ simile al BFS ma ora inseriamo i nodi in uno stack. Inoltre controlliamo se un nodo รจ giร  stato visitato allโ€™estrazione di esso, non allโ€™inserimento, altrimenti torneremmo su nodi giร  visitati.

void DFS(vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    stack<int> stack;

    for(int i = 0; i < graph.size(); i++) {
        stack.push(i);
        while(!stack.empty()) {
            int node = stack.top();
            stack.pop();
            if(!visited.at(node)) {
                cout << node << " ";
                visited.at(node) = true;
                for(int adj : graph.at(node)) {  
                    stack.push(adj);
                }
            }
        }
    }
    cout << endl;
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

๐Ÿ“ Definizioni

  • Sottografo: Gโ€ฒ รจ un sottografo di G (Gโ€ฒโІG)โ‡”Vโ€ฒโІV e Eโ€ฒโІE
  • Massimale: Gโ€ฒ รจ massimale โ‡”โˆ„ un altro sottografo Gโ€ณ di G tale che Gโ€ณ รจ connesso e piรน grande di Gโ€ฒ (i.e. Gโ€ฒโІGโ€ณโІG)

ย 

  • Un grafo G=(V,E)
    • non orientato รจ connesso โ‡” ogni suo nodo รจ raggiungibile da ogni altro suo nodo
    • orientato รจ fortemente connesso โ‡” ogni suo nodo รจ raggiungibile da ogni altro suo nodo

ย 

  • Un grafo Gโ€ฒ=(Vโ€ฒ,Eโ€ฒ)
    • รจ una componente connessa di G (non orientato) โ‡” Gโ€ฒ รจ un sottografo connesso e massimale di G
    • รจ una componente fortemente connessa di G (orientato) โ‡” Gโ€ฒ รจ un sottografo connesso e massimale di G

ย 

  • Ciclo: In un grafo orientato G=(V,E), un ciclo C รจ una sequenza di nodi u0,u1,...,uk tale che (ui,ui+1)โˆˆE per 0โ‰คiโ‰คkโˆ’1 e u0=uk
    • in un grafo non orientato un ciclo ha lunghezza k>2
    • in un grafo orientato un ciclo ha lunghezza kโ‰ฅ2

ย 

  • Classificazione degli archi in un grafo:
Tipo di arco Definizione Implementazione
Arco dell'albero Ogni volta che si esamina un arco da un nodo marcato ad un nodo non marcato dt[v]==0
Arco in avanti Se, dato un arco (u,v), u รจ un antenato di v dt[u]<dt[v] and ft[v]โ‰ 0
Arco all'indietro Se, dato un arco (u,v), u รจ un discendente di v dt[u]>dt[v] and ft[v]==0
Arco di attraversamento Un arco dell'albero tra 2 nodi giร  marcati Tutti gli altri casi

ย 

  • Ordinamento topologico di un grafo:
    • Dato un grafo orientato aciclico (senza cicli) G, un ordinamento topologico di G รจ un ordinamento lineare dei suoi nodi tale che se (u,v)โˆˆE, allora u appare prima di v nellโ€™ordinamento.
      Nota:
      • Esistono piรน ordinamenti topologici
      • Se il grafo contiene un ciclo, non esiste un ordinamento topologico.

Esempio:

TopologicalSort.png700

ย 

  • Grafo trasposto:
    • Dato un grafo orientato G=(V,E), il grafo trasposto GT=(V,ET) ha gli stessi nodi e gli archi orientati in senso opposto: ET={(u,v)|(v,u)โˆˆE}

๐Ÿ”„ Cicli

Dopo aver dato una definizione di ciclo, vediamo come implementare una funzione per determinarne se รจ presente un ciclo in un determinato grafo.

Grafi non orientati

Per i grafi non orientati รจ sufficiente eseguire un DFS facendo attenzione a non visitare nuovamente il nodo da cui si era arrivati, altrimenti verrebbe generato un falso positivo.

Implementazione

bool hasCycle(vector<vector<int> >& undirected_graph) {
    vector<bool> visited(undirected_graph.size(), false);
    for(int node = 0; node < undirected_graph.size(); node++) {
        /* In case that graph has more than 1 connected component */
        if(!visited.at(node))
            if(hasCycleHelper(undirected_graph, node, -1, visited))
                return true;
    }
    return false;
}

bool hasCycleHelper(vector<vector<int> >& undirected_graph, int node, int parent, vector<bool>& visited) {
    visited.at(node) = true;
    for(int adj : undirected_graph.at(node)) {
        if(adj != parent) {
            if(visited.at(adj))
                return true;
            else if(hasCycleHelper(undirected_graph, adj, node, visited))
                return true;
        }
    }
    return false;
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

Grafi orientati

Per i grafi orientati invece รจ piรน complicato, visto che se troviamo un nodo giร  visitato non รจ detto che il grafo contenga un ciclo.

Esempio:

graph TB
        A((a))
        B((b))
        C((c))
        
        A-->B
        B-->C
        A-->C

Se questo grafo non fosse orientato conterrebbe un ciclo!
Dobbiamo allora trovare un altro sistema, classificando cioรจ gli archi del grafo analizzato.
Se troviamo un arco all'indietro il grafo contiene un ciclo.

Implementazione

Quando viene individuato un arco allโ€™indietro, questo causa la restituzione di true in una chiamata e la conseguente restituzione di true da parte di tutte le chiamate ricorsive precedenti.

bool hasCycle(vector<vector<int> >& directed_graph) {
    /* discovery time of every node */
    vector<int> dt(directed_graph.size(), 0);
    /* finish time of every node */
    vector<int> ft(directed_graph.size(), 0);
    int time = 0;
    for(int node = 0; node < directed_graph.size(); node++) {
        /* in case that graph is a forest */
        if(dt.at(node) == 0)
            if(hasCycleHelper(directed_graph, node, time, dt, ft))
                return true;
    }
    return false;
}

bool hasCycleHelper(vector<vector<int> >& directed_graph, int node, int& time, vector<int>& dt, vector<int>& ft) {
    ++time;
    dt.at(node) = time;
    for(int adj : directed_graph.at(node)) {
        if(dt.at(adj) == 0)
            if(hasCycleHelper(directed_graph, adj, time, dt, ft))
                return true;
        /* back edge found */
        else if(dt.at(adj) < dt.at(node) && ft.at(adj) == 0)
            return true;
    }
    ++time;
    ft.at(node) = time;
    return false;
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

๐Ÿ“ถ Ordinamento topologico

Dopo aver dato una definizione di ordinamento topologico, vediamo come implementare una funzione per determinare l'ordinamento topologico di un grafo.

Grafi orientati

L'output sarร  una sequenza dei nodi, ordinati per tempo decrescente di fine. Ricordiamo che se il grafo contiene un ciclo, non esiste un ordinamento topologico.

Implementazione

  • Quando un nodo รจ "finito", tutti i suoi discendenti sono stati scoperti e aggiunti alla lista.
  • Aggiungendolo in testa alla lista, il nodo รจ in ordine corretto.
stack<int> topologicalSort(vector<vector<int> >& directed_graph) {
    vector<bool> visited(directed_graph.size(), false);
    stack<int> stack;

    for(int node = 0; node < directed_graph.size(); node++) {
        if(!visited.at(node))
            ts_DFS(directed_graph, node, stack, visited);
    }
    return stack;
}

void ts_DFS(vector<vector<int> >& directed_graph, int node, stack<int>& stack, vector<bool>& visited) {
    visited.at(node) = true;
    for(int adj : directed_graph.at(node)) {
        if(!visited.at(adj))
            ts_DFS(directed_graph, adj, stack, visited);
    }
    stack.push(node);
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

๐Ÿ”— Componenti connesse e fortemente connesse

Dopo aver dato una definizione di componente connessa e fortemente connessa, vediamo come implementare una funzione per determinarne il numero in un grafo.

Grafi non orientati

Implementazione

Effettuiamo la DFS di ogni nodo ma quando un nodo non era stato scoperto incrementiamo il contatore. Alla fine esso sarร  il numero di componenti connesse. Per ogni nodo il vettore id restituisce il numero di componente connessa a cui il nodo appartiene.

int connectedComponents(vector<vector<int> >& undirected_graph) {
    /* id will map every node with his connected component */
    vector<int> id(undirected_graph.size(), 0);
    int counter = 0;
    for(int node = 0; node < undirected_graph.size(); node++) {
        if(id.at(node) == 0) {
            ++counter;
            DFS(undirected_graph, node, id, counter);
        }
    }
    return counter;
}

void DFS(vector<vector<int> >& undirected_graph, int node, vector<int> & id, int counter) {
    id.at(node) = counter;
    for(int adj : undirected_graph.at(node)) {
        if(id.at(adj) == 0)
            DFS(undirected_graph, adj, id, counter);
    }
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

Grafi orientati

Per i grafi orientati invece รจ piรน complicato, visto che se utilizzassimo un semplice DFS il numero di componenti connesse dipenderebbe dal nodo di partenza. Dobbiamo allora trovare un altro sistema, usando cioรจ l'algoritmo di Kosaraju.

Implementazione

L'algoritmo di Kosaraju si divide in 3 parti:

  1. Effettuare un ordinamento topologico del grafo
  2. Calcolare il grafo trasposto del grafo di partenza
  3. A questo punto si puรฒ utilizzare lo stesso procedimento utilizzato nei grafi non orientati per calcolare il numero di componenti connesse. Attenzione perรฒ, invece di esaminare i nodi in ordine arbitrario, questa versione li esamina nellโ€™ordine LIFO memorizzato nello stack
int connectedComponents(vector<vector<int> >& directed_graph) {
    stack<int> stack = topologicalSort(directed_graph);
    vector<vector<int> > transposed_graph = transpose(directed_graph);
    return cc_helper(transposed_graph, stack);
}

stack<int> topologicalSort(vector<vector<int> >& directed_graph) {
    vector<bool> visited(directed_graph.size(), false);
    stack<int> stack;

    for(int node = 0; node < directed_graph.size(); node++) {
        if(!visited.at(node))
            ts_DFS(directed_graph, node, stack, visited);
    }
    return stack;
}

void ts_DFS(vector<vector<int> >& directed_graph, int node, stack<int>& stack, vector<bool>& visited) {
    visited.at(node) = true;
    for(int adj : directed_graph.at(node)) {
        if(!visited.at(adj))
            ts_DFS(directed_graph, adj, stack, visited);
    }
    stack.push(node);
}

vector<vector<int> > transpose(vector<vector<int> >& directed_graph) {
    vector<vector<int> > transposed_graph(directed_graph.size());
    for(int node = 0; node < directed_graph.size(); node++) {
        for(int adj : directed_graph.at(node)) {
            transposed_graph.at(adj).push_back(node);
        }
    }
    return transposed_graph;
}

int cc_helper(vector<vector<int> >& directed_graph, stack<int> stack) {
    vector<int> id(directed_graph.size(), 0);
    int counter = 0;
    while(!stack.empty()) {
        int node = stack.top();
        stack.pop();
        if(id.at(node) == 0) {
            ++counter;
            DFS_cc(directed_graph, node, id, counter);
        }
    }
    return counter;
}

void DFS_cc(vector<vector<int> >& graph, int node, vector<int> & id, int counter) {
    id.at(node) = counter;
    for(int adj : graph.at(node)) {
        if(id.at(adj) == 0)
            DFS_cc(graph, adj, id, counter);
    }
}
  • Time complexity: O(m+n) (n รจ il numero di nodi, m il numero di archi)
  • Space complexity: O(n)

  1. dove m=โˆ‘uโˆˆVย dout(u) (dout รจ lโ€™out-degree del nodo u) โ†ฉ๏ธŽ