Grafi
Indice
- โก๏ธ Grafo orientato (directed)
- โ๏ธ Grafo non orientato (undirected)
- โ๏ธ Proprietร dei grafi
- โจ๏ธ Implementazione
- ๐ Visita di un grafo
- ๐ Definizioni
โก๏ธ Grafo orientato (directed)
ร una coppia
รจ un insieme di nodi (node) o vertici (vertex) รจ un insieme di coppie ordinate di nodi dette archi o lati (edge)
Esempio
Input:
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
รจ un insieme di nodi (node) o vertici (vertex) รจ un insieme di coppie non ordinate di nodi dette archi o lati (edge)
Esempio
Input:
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
: numero di nodi : numero di archi
Alcune relazioni fra
- in un grafo non orientato,
- in un grafo orientato,
- in un grafo orientato aciclico, il numero massimo di archi che possono essere contenuti senza creare un ciclo รจ
Complessitร di algoritmi su grafi:
- La complessitร รจ espressa in termini sia di
che di (ad es. )
โจ๏ธ Implementazione
Matrici di adiacenza
Utilizziamo una matrice per implementare il grafo, ogni cella ha la seguente regola:
Grafi orientati
Utilizziamo l'intera matrice, lo spazio utilizzato sarร
Grafi non orientati
Utilizziamo metร matrice, lo spazio utilizzato sarร comunque
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.
oppure - Al posto di
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
Grafi orientati
Dobbiamo inserire gli archi tra i nodi una solta volta, lo spazio utilizzato sarร di
Grafi non orientati
Dobbiamo inserire gli archi tra i nodi due volte, lo spazio utilizzato sarร di
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.
oppure - Nella lista di nodi adiacenti avremo anche un campo peso in ogni nodo.
Per riassumere
| Matrici di adiacenza | Liste di adiacenza |
|---|---|
| Spazio richiesto: |
Spazio richiesto: |
| Verificare se u รจ adiacente a v richiede tempo |
Verificare se |
| Iterare su tutti gli archi richiede tempo |
Iterare su tutti gli archi richiede tempo |
| Ideale per grafi densi | Ideale per grafi sparsi |
๐ Visita di un grafo
Dato un grafo
| 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
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
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:
(n รจ il numero di nodi, m il numero di archi[1]) - Space complexity:
๐ข 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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
๐ Definizioni
- Sottografo:
รจ un sottografo di e - Massimale:
รจ massimale un altro sottografo di tale che รจ connesso e piรน grande di (i.e. )
ย
- Un grafo
- 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
- รจ una componente connessa di
(non orientato) โ รจ un sottografo connesso e massimale di - รจ una componente fortemente connessa di
(orientato) โ รจ un sottografo connesso e massimale di
- รจ una componente connessa di
ย
- Ciclo: In un grafo orientato
, un ciclo รจ una sequenza di nodi tale che per e - in un grafo non orientato un ciclo ha lunghezza
- in un grafo orientato un ciclo ha lunghezza
- in un grafo non orientato un ciclo ha lunghezza
ย
- 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 | |
| Arco in avanti | Se, dato un arco |
|
| Arco all'indietro | Se, dato un arco |
|
| 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)
, un ordinamento topologico di รจ un ordinamento lineare dei suoi nodi tale che se , allora appare prima di nellโordinamento.
Nota:- Esistono piรน ordinamenti topologici
- Se il grafo contiene un ciclo, non esiste un ordinamento topologico.
- Dato un grafo orientato aciclico (senza cicli)
Esempio:
/%E2%9A%99%EF%B8%8F%20Algoritmi%20e%20Strutture%20Dati/_images/TopologicalSort.png)
ย
- Grafo trasposto:
- Dato un grafo orientato
, il grafo trasposto ha gli stessi nodi e gli archi orientati in senso opposto:
- Dato un grafo orientato
๐ 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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
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-->CSe 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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
๐ถ 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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
๐ 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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
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:
- Effettuare un ordinamento topologico del grafo
- Calcolare il grafo trasposto del grafo di partenza
- 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:
(n รจ il numero di nodi, m il numero di archi) - Space complexity:
dove
( รจ lโout-degree del nodo ) โฉ๏ธ