Grafi

Indice

โžก๏ธ Grafo orientato (directed)

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

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:

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

Alcune relazioni fra n e m:

Complessitร  di algoritmi su grafi:

โŒจ๏ธ 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

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

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:

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

๐Ÿ”ข 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;
}

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

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

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

๐Ÿ“ Definizioni

ย 

ย 

ย 

ย 

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

ย 

Esempio:

TopologicalSort.png700

ย 

๐Ÿ”„ 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;
}

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

๐Ÿ“ถ 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

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

๐Ÿ”— 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);
    }
}

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

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