T - Grafi Flashcards
Definizione di ADT Grafo statico, semi-statico, dinamico.
- statico: non cambia
- semi-statico: si possono cancellare solo gli archi
- dinamico: si può cancellare tutto
Rappresentazioni possibili degli archi: descrizione, complessità spaziale, vantaggi e svantaggi.
1) Matrice di adiacenza: è una matrice adj |V| x |V| in cui l’elemento (i, j) vale 1 (o il peso nel caso di un grafo pesato) se l’arco (i, j) appartiene ad E.
È una matrice simmetrica se il grafo è non orientato.
È svantaggioso perché la complessità spaziale è S(n) = Theta(|V|^2).
È vantaggiosa perché non ci sono costi aggiuntivi per i grafi pesati e perché la lettura è diretta, O(1).
2) Lista di adiacenza: è un vettore A di |V| elementi in cui ogni elemento A[i] contiene il puntatore alla lista dei vertici adiacenti a i.
Gli elementi complessivi nelle liste sono al massimo 2|E| per i grafi non orientati e |E| per quelli orientati, per cui S(n) = O(max(|V|, |E|)) = O(|V + E|), e per questo è vantaggioso.
È svantaggioso perché c’è bisogno di un campo aggiuntivo per i pesi e perché la ricerca comporta la scansione della lista.
Come sono organizzati i file per l’elaborazione di un grafo? E le strutture dati? (da aggiornare con le altre slide dei grafi)
Bisogna lavorare con il main (client), con i file per i grafi e con quelli per la conversione indice_vertice <–> nome_vertice
main.c
#include
Graph.h
#include
typedef struct { int v; int w; int wt; } Edge;
typedef struct graph *Graph;
Graph.c
#include
// se si usa la lista delle adiacenze:
typedef struct node* link;
struct node {int v; int wt; link next; };
struct graph { int V; int E; link *ladj; ST tab; link z; };
// mentre se si usa la matrice delle adiacenze:
struct graph { int V; int E; int **mat; ST tab; };
ST.h
typedef struct symbtab *ST;
ST.c
struct symbtab {char **a; int MAXN; int N; }
GRAFI ORIENTATI E NON, LISTA DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHinit(int V);
- void GRAPHfree(Graph G);
Graph.h
typedef struct edge {int v; int w; //int wt; } Edge;
typedef struct graph *Graph;
Graph GRAPHinit(int V);
void GRAPHfree(Graph G);
Graph.c
typedef struct node * link;
struct node {int v; //int wt; link next; };
struct graph {int V; int E; link *ladj; ST tab; link z; };
Graph GRAPHinit(int V){
Graph g = malloc(sizeof(*g));
if (g == NULL) return NULL;
g->V = V;
g->E = 0;
g->z = NEW(-1, 0, NULL);
g->ladj = malloc(V *sizeof(link));
if (g->ladj == NULL) return NULL;
for (int i = 0; i < g->V; i++){
g->ladj[i] = z;
}
g->tab = STinit(V);
return g;
}
void GRAPHfree(Graph G){
link t;
for (int i = 0; i < G->V; i++){
for (link x = G->ladj[i]; x != G->z; x = t){
t = x->next;
free(x);
}
}
free(G->ladj);
STfree(tab);
free(z);
free(G);
}
GRAFI ORIENTATI E NON, LISTA DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHload(FILE *fin);
Graph.h
typedef struct edge {int v; int w; //int wt; } Edge;
typedef struct graph *Graph;
Graph GRAPHload(FILE *fin);
Graph.c
typedef struct node * link;
struct node {int v; //int wt; link next; };
struct graph {int V; int E; link *ladj; ST tab; link z; };
Graph GRAPHload(FILE *fin){
Graph G;
int V, i, wt;
char label1[MAX], label2[MAX];
fscanf(fin, “%d”, &V);
G = GRAPHinit(V);
for (i = 0; i < V; i++){
fscanf(fin, “%s”, label1);
STinsert(G->tab, label1, i);
}
while (fscanf(fin, “%s %s %d”, label1, label2, &wt) == 3){
id1 = STsearch(G->tab, label1);
id2 = STsearch(G->tab, label2);
if (id1 >= 0 && id2 >=0) GRAPHinsertE(G, id1, id2, wt);
}
}
void GRAPHinsertE(Graph G, int id1, int id2, int wt) {
insertE(G, EDGEcreate(id1, id2, wt));
}
static Edge EDGEcreate(int v, int w, int wt) {
Edge e;
e.v = v; e.w = w; e.wt = wt;
return e;
}
// NON ORIENTATI
static void insertE(Graph G, Edge e) {
int v = e.v, w = e.w, wt = e.wt;
G->ladj[v] = NEW(w, wt, G->ladj[v]);
G->ladj[w] = NEW(v, wt, G->ladj[w]);
G->E++;
}
//ORIENTATI
static void insertE(Graph G, Edge e) {
int v = e.v, w = e.w, wt = e.wt;
G->ladj[v] = NEW(w, wt, G->ladj[v]);
G->E++;
}
GRAFI ORIENTATI E NON, LISTA DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- void GRAPHstore(Graph G, FILE *fout);
- void GRAPHedges(Graph G, Edge *a);
Graph.h
typedef struct edge {int v; int w; //int wt; } Edge;
typedef struct graph *Graph;
Graph GRAPHload(FILE *fin);
Graph.c
typedef struct node * link;
struct node {int v; //int wt; link next; };
struct graph {int V; int E; link *ladj; ST tab; link z; };
void GRAPHstore(Graph G, FILE *fout) {
int i;
Edge *a;
a = malloc(G->E * sizeof(Edge));
if (a == NULL) return;
GRAPHedges(G, a);
fprintf(fout, “Numero vertici: %d\n”, G->V);
for (i = 0; i < G->V; i++)
fprintf(fout, “%s\n”, STsearchByIndex(G->tab, i));
for (i = 0; i < G->E; i++)
fprintf(fout, “%s %s %d\n”, STsearchByIndex(G->tab, a[i].v),
STsearchByIndex(G->tab, a[i].w), a[i].wt);
}
// NON ORIENTATI
void GRAPHedges(Graph G, Edge *a) {
int v, E = 0;
link t;
for (v=0; v < G->V; v++)
for (t=G->ladj[v]; t != G->z; t = t->next)
if (v < t->v)
a[E++] = EDGEcreate(v, t->v, t->wt);
}
// ORIENTATI
void GRAPHedges(Graph G, Edge *a) {
int v, E = 0;
link t;
for (v=0; v < G->V; v++)
for (t=G->ladj[v]; t != G->z; t = t->next)
a[E++] = EDGEcreate(v, t->v, t->wt);
}
GRAFI ORIENTATI E NON
Codice delle funzioni:
- int GRAPHgetIndex(Graph *G, char * label);
- void GRAPHremoveE(Graph G, int id1, int id2); (sia lista che matrice)
int GRAPHgetIndex(Graph G, char * label){
int id;
id = STsearch(G->tab, label);
if (id == -1) {
id = STsize(G->tab);
STinsert(G->tab, label, id);
}
return id;
}
void GRAPHremoveE(Graph G, int id1, int id2) {
removeE(G, EDGEcreate(id1, id2));
}
static void removeE(Graph G, Edge e) {
int v = e.v, w = e.w;
link x;
if (G->ladj[v]->v == w) {
G->ladj[v] = G->ladj[v]->next;
G->E–;
}
else
for (x = G->ladj[v]; x != G->z; x = x->next)
if (x->next->v == w) {
x->next = x->next->next;
G->E–;
}
// nei grafi orientati non c’è questa seconda parte
if (G->ladj[w]->v == v)
G->ladj[w] = G->ladj[w]->next;
else
for (x = G->ladj[w]; x != G->z; x = x->next)
if (x->next->v == v)
x->next = x->next->next;
}
static void removeE(Graph G, Edge e) {
int v = e.v, w = e.w, int wt = e.wt;
if (G->madj[v][w] != maxwt)
G->E–;
G->madj[v][w] = maxwt;
G->madj[w][v] = maxwt; // solo grafi non orientati
}
}
GRAFI ORIENTATI E NON, MATRICE DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHinit(int V);
- void GRAPHfree(Graph G);
Graph.h
#include
typedef struct graph * Graph;
typedef struct {int v; int w; int wt; } Edge;
Graph.c
#include
#define maxwt INT_MAX
struct graph { int V; int E; int **madj; ST tab; };
static int **MATRIXint(int r, int c, int val);
static int MATRIXint(int r, int c, int val){
int i, j;
int **m = malloc(rsizeof(int));
if (m == NULL) return NULL;
for (i = 0; i < r; i++){
m[i] = malloc(c*sizeof(int);
if (m[I] == NULL) return NULL;
}
for (i = 0; i < r; i++)
for(j = 0; j < c; j++)
m[i][j] = val;
return m;
}
Graph GRAPHinit(int V){
Graph G = malloc(sizeof(*G));
if (G == NULL) return NULL;
G->V = V;
G->E = 0;
G->madj = MATRIXint(V, V, maxwt);
if (G->madj == NULL) return NULL;
G->tab = STinit(V);
if (G->tab == NULL) return NULL;
return G;
}
void GRAPHfree(Graph G){
int i, j;
for (i = 0; i < G->V; i++) free(G->madj[i]);
free(G->madj);
STfree(G->tab);
free(G);
}
GRAFI ORIENTATI E NON, MATRICE DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHload(FILE *fin);
Graph GRAPHload(FILE *fin){
int V, id1, id2, wt;
char label1[MAX], label2[MAX];
fscanf(“%d”, &V);
Graph G = GRAPHinit(V);
for (int i = 0; i < V; i++){
fscanf(“%s”, label1);
STinsert(G->tab, label1, i);
}
while(fscanf(“%s %s %d”, label1, label2, &wt) == 3){
id1 = STsearch(G->tab, label1);
id2 = STsearch(G->tab, label2);
if(id1≥0 && id2≥0) GRAPHinsertE(G, id1, id2, wt);
}
return G;
}
void GRAPHinsertE(Graph G, int id1, int id2, int wt) {
insertE(G, EDGEcreate(id1, id2, wt));
}
static Edge EDGEcreate(int v, int w, int wt){
Edge e;
e.v = v; e.w = w; e.wt = wt;
return e;
}
static void insertE(Graph G, Edge e) {
int v = e.v, w = e.w, wt = e.wt;
if (G->madj[v][w] == maxWT) G->E++;
G->madj[v][w] = wt;
G->madj[w][v] = wt; // solo per grafi non orientati
}
GRAFI ORIENTATI E NON, MATRICE DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- void GRAPHstore(Graph G, FILE *fout);
- void GRAPHedges(Graph G, Edge *a);
void GRAPHstore(Graph G, FILE *fout) {
int i;
Edge *a = malloc(G->E * sizeof(Edge));
if (a == NULL) return;
GRAPHedges(G, a);
fprintf(fout, “Numero vertici: %d\n”, G->V);
for (i = 0; i < G->V; i++)
fprintf(fout, “%s\n”, STsearchByIndex(G->tab, i));
for (i = 0; i < G->E; i++)
fprintf(fout, “%s %s %d\n”, STsearchByIndex(G->tab, a[i].v),
STsearchByIndex(G->tab, a[i].w), a[i].wt);
}
void GRAPHedges(Graph G, Edge *a) {
int v, w, E = 0;
for (v=0; v < G->V; v++)
for (w=v+1; w < G->V; w++)
if (G->madj[v][w] != 0)
a[E++] = EDGEcreate(v, w, G->madj[v][w]);
}
// ORIENTATI
void GRAPHedges(Graph G, Edge *a) {
int v, w, E = 0;
for (v=0; v < G->V; v++)
for (w=0; w < G->V; w++)
if (G->madj[v][w] != 0)
a[E++] = EDGEcreate(v, w, G->madj[v][w]);
}
Quali strategie abbiamo studiato per la visita di un grafo?
- Depth First Search
- Breadth First Search
A cosa quali tipi di grafo è applicabile la visita DFS? Cosa genera?
La DFS è applicabile a grafi connessi e non.
Genera un albero della visita in profondità.
DFS: Cosa si intende con profondità?
Con profondità si intende l’espansione dell’ultimo vertice scoperto che ha ancora vertici non ancora scoperti a lui adiacenti.
DFS: Come vengono trattati i vertici?
La DFS parte da un vertice e visita tutti i vertici del grafo, sia che siano da essi raggiungibili che non.
Ogni vertice viene etichettato con il tempo di scoperta e con il tempo di fine elaborazione: pre[i] e post[i]
Per ogni vertice viene memorizzato il padre, ovvero il vertice a partire dal quale può essere raggiunto.
I vertici vengono rappresentati concettualmente come bianchi, grigi e neri.
DFS: come vengono etichettati gli archi?
Ogni arco può essere etichettato come T, B, F, C (solo T e B se il grafo è non orientato).
- T, tree: è il tipo di arco che si genera nella ricorsione
- B, backward: è l’arco che connette un vertice j a un suo antenato i per cui vale che post[i] == -1 ovvero non è ancora stato completato
- F, forward: connette un vertice i a un suo discendente j per cui si ha che pre[i] < pre[j]
- C: sono gli archi rimanenti
Scrivere il codice della void GRAPHdfs(Graph G, int id);(solowrapper)
void GRAPHdfs(Graph G, int id) {
int v, time=0, *pre, *post, *st;
pre = malloc(G->V * sizeof(int));
post = malloc(G->V * sizeof(int));
st = malloc(G->V * sizeof(int));
if ((pre == NULL) || (post == NULL) || (st == NULL)) return;
for (v=0; v < G->V; v++) {
pre[v] = -1; post[v] = -1; st[v] = -1;}
dfsR(G, EDGEcreate(id, id), &time, pre, post, st);
for (v=0; v < G->V; v++)
if (pre[v]== -1) dfsR(G, EDGEcreate(v,v), &time, pre, post, st);
printf(“discovery/endprocessing time labels \n”);
for (v=0; v < G->V; v++)
printf(“vertex %s : %d/%d \n”, STsearchByIndex(G->tab, v), pre[v],
post[v]);
printf(“resulting DFS tree \n”);
for (v=0; v < G->V; v++)
printf(“parent of vertex %s is vertex %s \n”, STsearchByIndex(G->tab,
v), STsearchByIndex(G->tab, st[v]));
}
Scrivere il codice della static void dfsR(Graph G, Edge e, int *time, int *pre, int *post, int *st);
static void dfsR(Graph G, Edge e, int *time, int *pre, int *post, int *st) {
link t;
int v, w = e.w;
Edge x;
if (e.v != e.w)
printf(“edge (%s, %s) is tree \n”, STsearchByIndex(G->tab, e.v),
STsearchByIndex(G->tab, e.w)) ;
st[e.w] = e.v;
pre[w] = (time)++;
for (t = G->ladj[w]; t != G->z; t = t->next)
if (pre[t->v] == -1)
dfsR(G, EDGEcreate(w, t->v), time, pre, post, st);
else {
v = t->v;
x = EDGEcreate(w, v);
if (post[v] == -1)
printf(“edge (%s, %s) is back \n”, STsearchByIndex(G->tab, x.v),
STsearchByIndex(G->tab, x.w));
else
if (pre[v]>pre[w])
printf(“edge (%s, %s) is forward \n”, STsearchByIndex(G->tab,
x.v), STsearchByIndex(G->tab, x.w));
else
printf(“edge (%s, %s) is cross \n”, STsearchByIndex(G->tab, x.v),
STsearchByIndex(G->tab, x.w));
}
post[w] = (time)++;
}
DFS: lista delle adiacenze
Complessità di inizializzazione, visita ricorsiva, tempo (lista e matrice)
- inizializzazione: Theta(V)
- visita ricorsiva: Theta(E)
- lista: T(n) = Theta(V+E)
- matrice: T(n): Theta(V^2)
BFS: a che tipo di visita porta
Dato un vertice di partenza, si visitano solo quelli da esso raggiungibili
BFS: cosa calcola di fatto?
Calcola la distanza minima dal vertice di partenza
BFS: cosa genera?
Un albero di visita in ampiezza
BFS: trattamento vertici
Ogni vertice viene etichettato con il tempo di scoperta pre[i] e per ogni vertice viene indicato il padre.
BFS: quale struttura dati viene utilizzata? Cosa permette?
Viene utilizzato un ADT di I classe coda e in base a come viene implementata varia la complessità.
La coda è una modalità seriale che permette di emulare un processo di visita dei vertici parallelo.
BFS: come vengono visitati i vertici?
In modo parallelo.
Codice della void GRAPHbfs(Graph G, int id); (solo wrapper)
void GRAPHbfs(Graph G, int id) {
int v, time=0, pre, st;
pre = malloc(G->Vsizeof(int));
st = malloc(G->Vsizeof(int));
if ((pre == NULL) || (st == NULL)) return;
for (v=0; v < G->V; v++) {
pre[v] = -1; st[v] = -1;
}
bfs(G, EDGEcreate(id,id), &time, pre, st);
printf(“\n Resulting BFS tree \n”);
for (v=0; v < G->V; v++)
if (st[v] != -1)
printf(“%s’s parent is: %s \n”, STsearchByIndex(G->tab, v),
STsearchByIndex(G->tab, st[v]));
}
Codice della static void bfs(Graph G, Edge e, int *time, int *pre, int *st);
static void bfs(Graph G, Edge e, int *time, int *pre, int st) {
int v;
Q q = Qinit();
Qput(q, e);
while (!Qempty(q))
if (pre[(e = Qget(q)).w] == -1) {
pre[e.w] = (time)++;
st[e.w] = e.v;
for (v = 0; v < G->V; v++)
if (G->madj[e.w][v] == 1)
if (pre[v] == -1)
Qput(q, EDGEcreate(e.w, v));
}
Qfree(q);
}
BFS: complessità della scansione nel caso della lista e della matrice
- lista: T(n) = O(V+E)
- matrice: T(n) = Theta(V^2)
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: Quando G è aciclico?
Quando non si incontrano archi di tipo B in una DFS
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: che tipo di implementazione si utilizza per la ricerca di CC in un grafo? In che tipo di grafo si cercano le CC?
Le componenti connesse si cercano in un grafo non orientato e per la ricerca si utilizza l’implementazione con la lista delle adiacenze
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: algoritmo concettuale per la ricerca di CC
In base a un indice si cerca per ogni vertice la componente connessa a cui appartiene (vettore int *cc). Se alla fine c’è una sola componente il grafo è connesso
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: codice della int GRAPHcc(Graph G);
int GRAPHcc(Graph G){
int v, id = 0, cc;
cc = malloc(G->Vsizeof(int));
if (cc == NULL) return -1;
for (v = 0; v < G->v; v++) cc[v] = -1;
for (v = 0; v < G->v; v++) {
if(cc[v] = -1) dfsRcc(G, v, id++, cc);
printf(“Componenti connesse: \n”);
for (v = 0; v < G->V; v++){
printf(“Il nodo %s appartiene alla cc %d \n”, STsearchbyindex(G->tab, v), cc[v]);
}
return id;
}
static void dfsRcc(Graph G, int v, int id, int *cc){
cc[v] = id;
for(link t = G->ladj[v]; t != G->z; t = t->next){
if (cc[t->v] == -1) dfsRcc(G, t->v, id, cc);
}
}
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: cosa vuol dire cercare la connettività? Su che tipo di grafo si cerca?
Cerchiamo la connettività su un grafo non orientato e connesso. Studiare la connettività vuol dire studiare i vertici e gli archi per i quali, se eliminati, il grafo si sconnette: sono i punti di articolazione e i ponti.
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: definizione di punto di articolazione
Un punto di articolazione è un punto che se eliminato sconnette il grafo.
Una radice lo è se ha almeno due figli.
Un vertice generico v lo è se v ha un figlio s e da s o da un suo discendente NON parte un arco B che va a un antenato proprio di v (se l’arco c’è rimane tutto collegato e non si sconnette nulla).
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: definizione di ponte
Un ponte è un arco che se eliminato sconnette il grafo.
Un arco B non è mai un ponte.
Un arco T (v, w) lo è se non ci sono archi B che connettano un discendente di w a un antenato di v.
DAG: caratteristiche
Un DAG è un grafo orientato e aciclico.
È caratterizzato da due classi di nodi: sorgente e pozzo. I nodi sorgente hanno in_degree = 0, i nodi pozzo hanno out_degree = 0.
Ogni DAG ha sempre almeno un ordinamento topologico
DAG: per cosa viene usato tipicamente?
Viene utilizzato per gli ordinamenti parziali -> problemi di scheduling
DAG: quali sono le operazioni tipiche?
Le operazioni tipiche sono gli ordinamenti topologici e gli ordinamenti tipologici inversi.
- ordinamenti topologici: riordinamento dei vertici secondo una linea orizzontale per cui dato un arco (u, v) si ha che sulla linea u sarà alla sx di v e quindi tutti gli archi andranno da sx a dx
- ordinamenti topologici inversi: archi da sx a dx quindi per (u, v) si avrà che u sarà alla destra di v
DAG: quando un ordinamento è unico?
Un ordinamento è unico quando esiste un cammino di Hamilton orientato: cammino semplice che tocca tutti i vertici
DAG: struttura dati per l’ordinamento topologico inverso
Viene utilizzato un grafo ADT di I classe implementato con la lista delle adiacenze.
- *pre: per ogni VERTICE viene indicato il tempo di scoperta
- *ts: per ogni TEMPO viene registrato quale vertice viene completato a quel tempo
- contenitore time: (contenitore ma di fatto è un int) per i tempi di ordinamento, avanza solo quando un vertice è completato
DAG: codice della void DAGrts(Dag D);
void DAGrts(Dag D){
int v, time = 0, *pre, *ts;
// allocazione, controllo e inizializzazione a -1
for (v = 0; v < D->V; v++)
if (pre[v] == -1) TSdfsR(D, v, ts, pre, &time);
printf(“Vertici del DAG in ordine topologico inverso: \n”);
for (v = 0; i < D->V; v++)
printf(“%s “, STsearcchbyIndex(D->tab, ts[v]));
}
static void TSdfsR(Dag D, int v, int *pre, int *ts, time){
link t;
pre[v] = 0;
for (t = D->ladj[v]; t != D->z; t. =t->next){
if (pre[t->v] == -1) TSdfsR(D, t->v, pre, ts, time);
}
ts[(time)++] = v;
}
DAG: per l’ordinamento topologico quale implementazione del grafo si usa?
Grafo ordinato con matrice delle adiacenze.
DAG: concettualmente come si realizza l’ordinamento topologico inverso?
SI invertono i riferimenti riga-colonna.
DAG: codice della void DAGts(Dag D);
void DAGts(Dag D){
int v, time = 0, *pre, *ts;
// allocazione, controllo, inizializzazione a a-1;
for(v = 0; v < D->V; v++)
if (pre[v] == -1) TSdfsR(D, v, pre, ts, &time);
printf(“Vertici del DAG in ordine topologico \n”);
for (v = 0; D < D->V; v++)
printf(“%s”, STsearchByIndex(D->tab, ts[v]);
}
static void TSdfsR(Dag D, int v, int pre, intts, int time){
pre[v] = 0;
for (int w = 0; w < D->V; w++)
if (D->madj[w][v] != 0)
if (pre[w] == -1) TSdfsR(D, w, pre, ts, time);
ts[(time)++] = w;
}
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: quando un grafo orientato è fortemente connesso?
Un grafo orientato è fortemente connesso quando ha una sola componente fortemente connessa che è massimale.
APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: grazie a quale proprietà e come si arriva al Kernel DAG?
In una componente fortemente connessa i vertici godono della proprietà di essere mutuamente raggiungibili: se esiste il cammino da v a w esiste anche il cammino da w a v. Si possono quindi formare delle classi di equivalenza rispetto alla proprietà di mutua raggiungibilità. Tutti i vertici della SCC godono della stessa proprietà.
Quindi da ogni SCC può essere scelto un vertice rappresentativo e si può formare un G’ ridotto il quale gode della proprietà di essere un DAG: è detto Kernel DAG o DAG nucleare
ALGORITMO DI KOSARAJU: a cosa serve?
Serve a determinare le componenti fortemente connesse quindi è applicabile a un grafo orientato
ALGORITMO DI KOSARAJU: concetto
SI traspone il grafo G.
Si effettua una DFS sul grafo G^T che darà come risultato un vettore che contiene i vertici in base all’ordine in cui sono stati completati.
SI effettua una DFS su G considerando però, come ordine dei vertici, quello dato dal vettore derivante dalla DFS di G^T (postR in discesa)
Gli alberi della DFS di G sono le SCC.
ALGORITMO DI KOSARAJU: definizione di grafo trasposto
Dato un grafo G = (V, E), il suo trasposto G^T = (V, E^T) è tale per cui se (u, v) appartiene ad E allora (v, u) appartiene a E^T.
ALGORITMO DI KOSARAJU: codice della static Graph reverse(Graph G, Graph R);
static Graph reverse(Graph G, Graph R){
int v;
link t;
for (v = 0; v < D->V; v++)
for (t = G->ladj[v]; t != D->z; t = t->next)
GRAPHinsertE(R, t->v, v);
return R;
}
ALGORITMO DI KOSARAJU: struttura dati per la ricerca delle SCC
- *sccR per marcare i vertici visitati nella DFS del grafo trasposto
- *sccG per marcare i vertici visitati nella DFS del grafo G; i numeri con cui i vertici vengono marcati indicano in realtà la SCC a cui il vertice appartiene
- time0: contatore che avanza solo a fine elaborazione
- time1: contatore per le SCC
- *postR: al tempo i-esimo viene completato il vertice v-esimo e questa informazione si salva in questo vettore nella forma post[tempo i-esimo] = v-esimo
- *postG: per uniformità in modo da poter usare la stessa funzione ricorsiva in entrambe le DFS
ALGORITMO DI KOSARAJU: codice della int GRAPHscc(Graph G);
int GRAPHscc(Graph G){
int v, time0 = 0, time1 = 0, *sccR, *sccG, *postR, *postG;
//allocazione, controllo, inzializzazione
Graph R;
R = GRAPHinit(G->V);
reverse(G, R);
for(v = 0; v < D->V; v++)
if (sccR[v] == -1) SCCdfsR(G, v, sccR, &time0, time1, postR);
time0 = 0; time1 = 0;
for(v = G->(V-1); v >= 0; v–)
if (sccG[postR[v]] == -1){
SCCdfsR(G, postR[v], sccG, &time0, time1, postG);
time1++;
}
GRAPHfree(R);
return time1;
}
static void SCCdfsR(Graph G, int w, int *scc, int *time0, int time1, int post){
scc[w] = time1;
for(t = G->ladj[w]; t != G->z; t = t->next)
if (scc[t->v] == -1)
SCCdfsR(G, t->v, sccc, time0, time1, post);
post[(time0)++] = w; // c’è solo questo in più rispetto alla cc
}
ALBERI RICOPRENTI MINIMI: su quale tipo di grafo li cerchiamo?
Grafi non orientati, pesati, connessi
ALBERI RICOPRENTI MINIMI: per estrarne uno da un grafo G, che caratteristiche deve avere?
Vogliamo estrarre G’ = (V, A) che sia ricoprente (infatti l’insieme V è lo stesso di G), che sia un albero quindi non abbia cicli, e che minimizzi la somma di tutti gli archi di A dove A è un sottoinsieme incluso o coincidente con E
ALBERI RICOPRENTI MINIMI: sigla inglese
Minimum Weight Spanning Tree MST
ALBERI RICOPRENTI MINIMI:
se un grafo è “____” allora è un albero
aciclico e copre tutti i vertici
ALBERI RICOPRENTI MINIMI: quando l’albero MST è unico?
quando i pesi degli archi sono tutti distinti
ALBERI RICOPRENTI MINIMI: possibili rappresentazioni dell’albero MST
1) vettore Edge *mst;
2) grafo rappresentato con le liste delle adiacenze
3) vettore int *st e int *wt in cui st contiene il padre e wt il peso dell’arco che va dal vertice a suo padre
ALBERI RICOPRENTI MINIMI: quale strategia si usa e come sarà la soluzione?
Strategia Greedy che in genere non dà una soluzione per forza ottima ma in questo caso sì.
ALBERI RICOPRENTI MINIMI: quando un arco è sicuro?
Un arco è sicuro quando aggiunto a un MST produce ancora un MST
ALBERI RICOPRENTI MINIMI: definizione di taglio. Quando un taglio rispetta un insieme di archi?
Considerato un grafo non orientato, pesato, connesso, un taglio è una partizione dell’insieme V in S e V-S tale per cui:
- V = {S} U {V-S}
- {S} intersezione {V-S} = insieme vuoto
Un taglio rispetta un insieme A di archi se nessun arco di A attraversa il taglio
ALBERI RICOPRENTI MINIMI: definizione di arco leggero
Un arco è leggero se ha peso minimo tra quelli che attraversano il taglio
ALBERI RICOPRENTI MINIMI: Teorema degli archi sicuri
Dato un grafo non orientato, pesato, connesso e un insieme di archi A, se:
- A è incluso o coincidente con E
- (S, V-S) è un taglio che rispetta A
- (u, v) è un arco leggero che attraversa il taglio
allora (u, v) è sicuro per A
ALBERI RICOPRENTI MINIMI: Corollario degli archi sicuri
Dato un grafo non orientato, pesato, connesso e un insieme di archi A, se:
- A è incluso o coincidente con E
- C è un albero nella foresta G_A
- (u, v) è un arco leggero che connette C ad un altro albero della foresta
allora (u, v) è sicuro per A
ADT UNION FIND: per cosa l’abbiamo studiata? A cosa serve in generale? In che versione?
Nella versione weighted quick-union serve in generale per memorizzare una collezione di insiemi disgiunti. La usiamo per implementare l’algoritmo di Kruskal per la ricerca di MST
ADT UNION FIND: quali operazioni la caratterizzano?
UFfind e UFunion
ADT UNION FIND: scrivere le strutture dati (file UF.h e UF.c)
UF.c
static int *id, *sz;
ADT UNION FIND: codice della void UFinit(int N);
UF.c
static int *id, *sz;
void UFinit(int N){
id = malloc(Nsizeof(int));
sz = malloc(Nsizeof(int));
for (int i = 0; i < N; i++){
id[i] = i; sz[i] = 1;
}
}
ADT UNION FIND: scrivere il codice di:
- int UFfind(int p, int q);
- void UFunion(int p, int q);
int UFfind(int p, int q){
return (find(p) == find(q));
}
int find(int i){
while (id[i] != i) i = id[i];
return i;
}
void UFunion(int p, int q){
int i = find(p), j = find(q);
if (I == j) return;
if (sz[I] < sz[j]) { id[i] = j; sz[j] += sz[i]};
else {id[j] = i; sz[i] += sz[j]}
}
ADT UNION FIND: complessità della Quick-union
O(1): assegnazione
ADT UNION FIND: complessità della quick-find
O(logN)
percorrimento catena e fusione dei sottoinsiemi in un cammino che diventa logaritmico
ALBERI RICOPRENTI MINIMI: algoritmi studiati per la loro ricerca
Kruskal e Prim
ALGORITMO DI KRUSKAL: quale teorema/corollario utilizza? Quale struttura dati?
Corollario degli archi sicuri e ADT Union-find
ALGORITMO DI KRUSKAL: passi dell’algoritmo
- si parte da una foresta di alberi ognuno corrispondente a un singolo vertice
- si ordinano gli archi per peso crescente
- si itera la selezione di un arco sicuro e lo si aggiunge se i suoi vertici non fanno parte dello stesso albero
- terminazione quando tutti i vertici sono stati considerati
ALGORITMO DI KRUSKAL: complessità
In generale O(|E|log|E|) ma considerando un grafo completo con |E| = |V|^2 allora T(n) = O(|E|log|V|)
ALGORITMO DI KRUSKAL: codice della void GRAPHmstK(Graph G);
void GRAPHmstK(Graph G){
int i, k, weight = 0;
Edge mst, a;
mst = malloc((G->V-1)sizeof(Edge));
a = malloc((G->E)sizeof(Edge));
k = mst(G, mst, a);
printf(“Archi nell’MST: “);
for(i = 0; i < k, i++){
printf(“%s-%s”, STsearchByIndex(G->tab, mst[I].v), STsearchByIndex(G->tab, mst[I].w))
weight += mst[I].wt;
}
printf(“Peso minimo: %d”, weight);
}
int mst(Graph G, Edge *mst, Edge *a){
int i, k;
GRAPHedges(G, a);
sort(a, 0, G->E-1);
UFinit(G->V); (ci sono le variabili statiche)
for(i = 0, k = 0; i < G->E && k < G->V-1; i++)
if(!UFfind(a[I].v, a[i].w)){
UFunion(a[I].v, a[i].w);
mst[k++] = a[i];
}
return k;
}
A cosa serve l’algoritmo di Kruskal?
Ricerca di un MST
A cosa serve l’algoritmo di Prim?
Ricerca di un MST
ALGORITMO DI PRIM: su che teorema/corollario si basa?
Teorema degli archi sicuri
ALGORITMO DI PRIM: algoritmo soluzione brute-force
Si parte da S vuoto, per V-1 passi di itera per trovare un arco con peso minimo tra quelli che attraversano il taglio e si aggiunge l’altro vertice a S. Termina quando tutti i vertici sono stati considerati
ALGORITMO DI PRIM: algoritmo migliorato
A ogni passo si aggiunge a S un vertice in base alla distanza minima che c’è tra un vertice di S e un vertice di V-S
ALGORITMO DI PRIM: strutture dati utilizzate e loro significato
- matrice delle adiacenze in cui un arco non esistente ha peso 0
- int *st di G->V elementi per registrare i padri
- int *fr di G->V elementi per registrare per ogni vertice di V-S il vertice di S più vicino
- int *wt di G->V+1 elementi per registrare per i vertici di S la distanza dal padre e per gli elementi di V-S il peso dell’arco con il vertice di S più vicino
- min per salvare il vertice di V-S più vicino a S
ALGORITMO DI PRIM: complessità
T(n) = O(|V|^2) per un grafo denso
T(n) = O(|E|log|V|)
ALGORITMO DI PRIM: codice della void GRAPHmstP(Graph G);
void GRAPHmstP(Graph G){
int v, weight = 0;
int st, wt;
st = malloc((G->V)sizeof(int));
wt = malloc((G->V+1)sizeof(int));
mstV(G, st, wt);
printf(“Archi nell’MST: “);
for(v = 0; v < G->V, v++)
if(st[v] != v){
printf(“%s-%s”, STsearchByIndex(G->tab, mst[I].v), STsearchByIndex(G->tab, mst[I].w))
weight += mst[i].wt;
}
printf(“Peso minimo: %d”, weight);
}
void mstV(Graph G, int *st, int *wt){
int v, w, min fr = malloc(G->Vsizeof(int));
for(v = 0; v < G->V; v++) { st[v] = -1; fre[v] = v; wt[v] = maxWT; }
st[0] = 0; wt[0] = 0; wt[G->V] = maxWT;
for(min = 0; min != G->V; ){
v = min; st[min] = fr[min];
for(w = 0, min = G->V; w < G->V; w++)
if(st[w] == -1){
if(G->madj[v][w] < wt[w]) {wt[w] = G->madj[v][w]; fr[w] = v;}
if(wt[w] < wt[min]) min = w;
}
}
}
CAMMINI MINIMI: su quali grafi si cercano?
Su grafi orientati e pesati
CAMMINI MINIMI: definizione di peso di un cammino
w(p) = sum (i = 1, k) w(v_i-1, v_i)
CAMMINI MINIMI: definizione di peso di un cammino minimo
È il minimo tra i cammini che connettono s e v, infinito altrimenti
CAMMINI MINIMI: definizione di cammino minimo e caratteristiche
Qualsiasi cammino dove il peso del cammino è il peso minimo del cammino
Un cammino minimo non contiene cicli e ha al più V-1 archi.
CAMMINI MINIMI: casistiche in cui ci sono archi con peso negativo
- se ci sono archi con peso < 0 ma non ci sono cicli con peso < 0 allora Dijkstra non dà necessariamente una soluzione ottima mentre Bellman-Ford sì
- se ci sono archi con peso < 0 e ci sono anche cicli con peso < 0 allora il problema non ha senso mentre Bellman-Ford se ne accorge
CAMMINI MINIMI: perchè non ha senso che contengano un ciclo?
Nel caso di un ciclo negativo non ha senso perchè il problema perde di significato.
Nel caso di un ciclo positivo non ha senso perchè togliendo il ciclo ci sarebbe un cammino con peso minore
CAMMINI MINIMI: caratteristiche dell’approccio brute-force, programmazione dinamica, Greddy
- brute-force: enumerazione e check di tutti i sottoinsieme di archi, costo esponenziale; l’ordine conta. il check consiste nel controllare che sia un cammino e che il peso sia minimo
- programmazione dinamica: applicabile
CAMMINI MINIMI: definizione di rilassamento ed esempio
Lasciare che una soluzione violi un vincolo temporaneamente e poi eliminare la violazione
esempio: sovrastima del cammino
1. d[v] = maxWT
2. rilassamento di d[v] verificando se conviene il cammino, altrimenti cambiando il risultato
ALGORITMO DI DIJKSTRA: per cosa lo si usa
Per la ricerca dei cammini minimi su grafi orientati e pesati
ALGORITMO DI DIJKSTRA: strategia
Greedy
ALGORITMO DI DIJKSTRA: struttura dati
S insieme dei vertici per cui è stato calcolato il cammino minimo
V-S vertici. restanti in una PQ
ALGORITMO DI DIJKSTRA: algoritmo
- estrazione dalla coda (V-S) del vertice con distanza minima da S
- inserimento del vertice in S
- rilassamento di tutti gli archi uscenti dal vertice
fino a quando la coda ha elementi
ALGORITMO DI DIJKSTRA: complessità
- hp: coda implementata con heap (costi logaritmici)
- rilassamento degli archi O(|E|)
- in generale T(n) = O((|V|+|E|)log|V|)
- se tutti i vertici sono raggiungibili da s T(n) = O(|E|log|V|)
ALGORITMO DI DIJKSTRA: codice della void GRAPHspD(Graph G, int id);
void GRAPHspD(Graph G, int id) {
int v;
link t;
PQ pq = PQinit(G->V);
int st, mindist;
st = malloc(G->Vsizeof(int));
mindist = malloc(G->Vsizeof(int));
if ((st == NULL) || (mindist == NULL)) return;
for (v = 0; v < G->V; v++){
st[v] = -1;
mindist[v] = maxWT;
PQinsert(pq, mindist, v);
}
mindist[id] = 0;
st[id] = id;
PQchange(pq, mindist, id);
while (!PQempty(pq)) {
if (mindist[v = PQextractMin(pq, mindist)] != maxWT) {
for (t=G->ladj[v]; t!=G->z ; t=t->next)
if (mindist[v] + t->wt < mindist[t->v]) {
mindist[t->v] = mindist[v] + t->wt;
PQchange(pq, mindist, t->v);
st[t->v] = v;
}
}
}
printf(“\n Shortest path tree\n”);
for (v = 0; v < G->V; v++)
printf(“parent of %s is %s \n”, STsearchByIndex(G->tab, v),
STsearchByIndex(G->tab, st[v]));
printf(“\n Minimum distances from node %s\n”, STsearchByIndex(G->tab,
id));
for (v = 0; v < G->V; v++)
printf(“mindist[%s] = %d \n”, STsearchByIndex(G->tab, v), mindist[v]);
PQfree(pq);
}
CAMMINI MINIMI: caso dei DAG
I DAG sono per costruzione aciclici quindi l’algoritmo è semplificato e si possono cercare sia cammini minimi che massimi con complessità O(|V| + |E|). La prima cosa da fare è un ordinamento topologico. La relaxation parte dal risultato dell’ordinamento in entrambi i casi
ALGORITMO DI BELLMAN-FORD: per cosa lo usiamo?
per la ricerca dei cammini minimi nel caso ci siano archi a peso negativo
ALGORITMO DI BELLMAN-FORD: strategia
Programmazione dinamica, calcolo bottom-up della soluzione
ALGORITMO DI BELLMAN-FORD: soluzione ricorsiva d’ispirazione
- terminazione: quando d[v] = 0 perchè v coincide con il vertice di partenza (una vertice è a distanza 0 da se stesso)
- per un vertice v, la distanza dal vertice sorgente deve essere minima e quindi bisogna scegliere tra:
1. d[v]
2. il cammino minimo che c’è da s a u dove u è uno dei vertici che attraverso un arco incidono in v ovvero d[u] + w(u, v)
Quindi se d[v] < d[u] + w(u, v) si sceglie d[v] e viceversa
ALGORITMO DI BELLMAN-FORD: algoritmo
In V-1 passi: al passo i-esimo si attua un ciclo di. rilassamento sugli archi in avanti
al passo V esimo, se il risultato diminuisce ancora, vuol dire che c’è un ciclo a peso negativo
Se il peso rimane fisso da un passo all’altro terminazione anticipata-> soluzione ottima
ALGORITMO DI BELLMAN-FORD: complessità
T(n) = O(|V||E|)
ALGORITMO DI BELLMAN-FORD: codice della void GRAPHspBF(Graph G, int id);
void GRAPHspBF(Graph G, int id){
int v, w, negcycfound;
link t;
int st, mindist;
st = malloc(G->Vsizeof(int));
mindist = malloc(G->Vsizeof(int));
if ((st == NULL) || (mindist == NULL)) return;
for ( v = 0; v < G->V; v++) {
st[v]= -1;
mindist[v] = maxWT;
}
mindist[id] = 0;
st[id] = id;
for (w = 0; w < G->V - 1; w++)
for (v = 0; v < G->V; v++)
if (mindist[v] < maxWT)
for (t = G->ladj[v]; t != G->z ; t = t->next)
if (mindist[t->v] > mindist[v] + t->wt) {
mindist[t->v] = mindist[v] + t->wt;
st[t->v] = v;
}
negcycfound = 0;
for (v = 0; v < G->V; v++)
if (mindist[v] < maxWT)
for (t = G->ladj[v]; t != G->z ; t = t->next)
if (mindist[t->v] > mindist[v] + t->wt)
negcycfound = 1;
if (negcycfound == 0) {
printf(“\n Shortest path tree\n”);
for (v = 0; v < G->V; v++)
printf(“Parent of %s is %s \n”, STsearchByIndex(G->tab, v),
STsearchByIndex(G->tab, st[v]));
printf(“\n Minimum distances from node %s\n”, STsearchByIndex(G->tab,
id));
for (v = 0; v < G->V; v++)
} printf(“mindist[%s] = %d \n”, STsearchByIndex(G->tab, v), mindist[v]);
else
printf(“\n Negative cycle found!\n”);
}
Come viene implementata la PQ per Dijkstra?
Vettore di indici in cui la prio è data dalla mindist
