T - Grafi

Question 1

Definizione di ADT Grafo statico, semi-statico, dinamico.

Answer 1

• statico: non cambia
• semi-statico: si possono cancellare solo gli archi
• dinamico: si può cancellare tutto

Question 2

Rappresentazioni possibili degli archi: descrizione, complessità spaziale, vantaggi e svantaggi.

Answer 2

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.

Question 3

Come sono organizzati i file per l’elaborazione di un grafo? E le strutture dati? (da aggiornare con le altre slide dei grafi)

Answer 3

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

Question 4

GRAFI ORIENTATI E NON, LISTA DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHinit(int V);
- void GRAPHfree(Graph G);

Answer 4

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

Question 5

GRAFI ORIENTATI E NON, LISTA DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHload(FILE *fin);

Answer 5

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

Question 6

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

Answer 6

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

Question 7

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)

Answer 7

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

Question 8

GRAFI ORIENTATI E NON, MATRICE DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHinit(int V);
- void GRAPHfree(Graph G);

Answer 8

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

Question 9

GRAFI ORIENTATI E NON, MATRICE DELLE ADIACENZE (pesati e non)
Scrivere il codice delle seguenti funzioni:
- Graph GRAPHload(FILE *fin);

Answer 9

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
}

Question 10

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

Answer 10

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

Question 11

Quali strategie abbiamo studiato per la visita di un grafo?

Answer 11

• Depth First Search
• Breadth First Search

Question 12

A cosa quali tipi di grafo è applicabile la visita DFS? Cosa genera?

Answer 12

La DFS è applicabile a grafi connessi e non.
Genera un albero della visita in profondità.

Question 13

DFS: Cosa si intende con profondità?

Answer 13

Con profondità si intende l’espansione dell’ultimo vertice scoperto che ha ancora vertici non ancora scoperti a lui adiacenti.

Question 14

DFS: Come vengono trattati i vertici?

Answer 14

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.

Question 15

DFS: come vengono etichettati gli archi?

Answer 15

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

Question 16

Scrivere il codice della void GRAPHdfs(Graph G, int id);(solowrapper)

Answer 16

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

Question 17

Scrivere il codice della static void dfsR(Graph G, Edge e, int *time, int *pre, int *post, int *st);

Answer 17

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

Question 18

DFS: lista delle adiacenze
Complessità di inizializzazione, visita ricorsiva, tempo (lista e matrice)

Answer 18

• inizializzazione: Theta(V)
• visita ricorsiva: Theta(E)
• lista: T(n) = Theta(V+E)
• matrice: T(n): Theta(V^2)

Question 19

BFS: a che tipo di visita porta

Answer 19

Dato un vertice di partenza, si visitano solo quelli da esso raggiungibili

Question 20

BFS: cosa calcola di fatto?

Answer 20

Calcola la distanza minima dal vertice di partenza

Question 21

BFS: cosa genera?

Answer 21

Un albero di visita in ampiezza

Question 22

BFS: trattamento vertici

Answer 22

Ogni vertice viene etichettato con il tempo di scoperta pre[i] e per ogni vertice viene indicato il padre.

Question 23

BFS: quale struttura dati viene utilizzata? Cosa permette?

Answer 23

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.

Question 24

BFS: come vengono visitati i vertici?

Answer 24

In modo parallelo.

Question 25

Codice della void GRAPHbfs(Graph G, int id); (solo wrapper)

Answer 25

void GRAPHbfs(Graph G, int id) { int v, time=0, *pre, *st; pre = malloc(G->V*sizeof(int)); st = malloc(G->V*sizeof(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])); }

Question 26

Codice della static void bfs(Graph G, Edge e, int *time, int *pre, int *st);

Answer 26

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

Question 27

BFS: complessità della scansione nel caso della lista e della matrice

Answer 27

- lista: T(n) = O(V+E) - matrice: T(n) = Theta(V^2)

Question 28

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: Quando G è aciclico?

Answer 28

Quando non si incontrano archi di tipo B in una DFS

Question 29

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?

Answer 29

Le componenti connesse si cercano in un grafo non orientato e per la ricerca si utilizza l'implementazione con la lista delle adiacenze

Question 30

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: algoritmo concettuale per la ricerca di CC

Answer 30

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

Question 31

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: codice della int GRAPHcc(Graph G);

Answer 31

int GRAPHcc(Graph G){ int v, id = 0, *cc; cc = malloc(G->V*sizeof(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); } }

Question 32

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: cosa vuol dire cercare la connettività? Su che tipo di grafo si cerca?

Answer 32

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.

Question 33

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: definizione di punto di articolazione

Answer 33

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

Question 34

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: definizione di ponte

Answer 34

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.

Question 35

DAG: caratteristiche

Answer 35

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

Question 36

DAG: per cosa viene usato tipicamente?

Answer 36

Viene utilizzato per gli ordinamenti parziali -> problemi di scheduling

Question 37

DAG: quali sono le operazioni tipiche?

Answer 37

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

Question 38

DAG: quando un ordinamento è unico?

Answer 38

Un ordinamento è unico quando esiste un cammino di Hamilton orientato: cammino semplice che tocca tutti i vertici

Question 39

DAG: struttura dati per l'ordinamento topologico inverso

Answer 39

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

Question 40

DAG: codice della void DAGrts(Dag D);

Answer 40

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

Question 41

DAG: per l'ordinamento topologico quale implementazione del grafo si usa?

Answer 41

Grafo ordinato con matrice delle adiacenze.

Question 42

DAG: concettualmente come si realizza l'ordinamento topologico inverso?

Answer 42

SI invertono i riferimenti riga-colonna.

Question 43

DAG: codice della void DAGts(Dag D);

Answer 43

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, int*ts, 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; }

Question 44

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: quando un grafo orientato è fortemente connesso?

Answer 44

Un grafo orientato è fortemente connesso quando ha una sola componente fortemente connessa che è massimale.

Question 45

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: grazie a quale proprietà e come si arriva al Kernel DAG?

Answer 45

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

Question 46

ALGORITMO DI KOSARAJU: a cosa serve?

Answer 46

Serve a determinare le componenti fortemente connesse quindi è applicabile a un grafo orientato

Question 47

ALGORITMO DI KOSARAJU: concetto

Answer 47

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.

Question 48

ALGORITMO DI KOSARAJU: definizione di grafo trasposto

Answer 48

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.

Question 49

ALGORITMO DI KOSARAJU: codice della static Graph reverse(Graph G, Graph R);

Answer 49

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

Question 50

ALGORITMO DI KOSARAJU: struttura dati per la ricerca delle SCC

Answer 50

- *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

Question 51

ALGORITMO DI KOSARAJU: codice della int GRAPHscc(Graph G);

Answer 51

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 }

Question 52

ALBERI RICOPRENTI MINIMI: su quale tipo di grafo li cerchiamo?

Answer 52

Grafi non orientati, pesati, connessi

Question 53

ALBERI RICOPRENTI MINIMI: per estrarne uno da un grafo G, che caratteristiche deve avere?

Answer 53

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

Question 54

ALBERI RICOPRENTI MINIMI: sigla inglese

Answer 54

Minimum Weight Spanning Tree MST

Question 55

ALBERI RICOPRENTI MINIMI: se un grafo è "____" allora è un albero

Answer 55

aciclico e copre tutti i vertici

Question 56

ALBERI RICOPRENTI MINIMI: quando l'albero MST è unico?

Answer 56

quando i pesi degli archi sono tutti distinti

Question 57

ALBERI RICOPRENTI MINIMI: possibili rappresentazioni dell'albero MST

Answer 57

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

Question 58

ALBERI RICOPRENTI MINIMI: quale strategia si usa e come sarà la soluzione?

Answer 58

Strategia Greedy che in genere non dà una soluzione per forza ottima ma in questo caso sì.

Question 59

ALBERI RICOPRENTI MINIMI: quando un arco è sicuro?

Answer 59

Un arco è sicuro quando aggiunto a un MST produce ancora un MST

Question 60

ALBERI RICOPRENTI MINIMI: definizione di taglio. Quando un taglio rispetta un insieme di archi?

Answer 60

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

Question 61

ALBERI RICOPRENTI MINIMI: definizione di arco leggero

Answer 61

Un arco è leggero se ha peso minimo tra quelli che attraversano il taglio

Question 62

ALBERI RICOPRENTI MINIMI: Teorema degli archi sicuri

Answer 62

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

Question 63

ALBERI RICOPRENTI MINIMI: Corollario degli archi sicuri

Answer 63

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

Question 64

ADT UNION FIND: per cosa l'abbiamo studiata? A cosa serve in generale? In che versione?

Answer 64

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

Question 65

ADT UNION FIND: quali operazioni la caratterizzano?

Answer 65

UFfind e UFunion

Question 66

ADT UNION FIND: scrivere le strutture dati (file UF.h e UF.c)

Answer 66

UF.c static int *id, *sz;

Question 67

ADT UNION FIND: codice della void UFinit(int N);

Answer 67

UF.c static int *id, *sz; void UFinit(int N){ id = malloc(N*sizeof(int)); sz = malloc(N*sizeof(int)); for (int i = 0; i < N; i++){ id[i] = i; sz[i] = 1; } }

Question 68

ADT UNION FIND: scrivere il codice di: - int UFfind(int p, int q); - void UFunion(int p, int q);

Answer 68

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

Question 69

ADT UNION FIND: complessità della Quick-union

Answer 69

O(1): assegnazione

Question 70

ADT UNION FIND: complessità della quick-find

Answer 70

O(logN) percorrimento catena e fusione dei sottoinsiemi in un cammino che diventa logaritmico

Question 71

ALBERI RICOPRENTI MINIMI: algoritmi studiati per la loro ricerca

Answer 71

Kruskal e Prim

Question 72

ALGORITMO DI KRUSKAL: quale teorema/corollario utilizza? Quale struttura dati?

Answer 72

Corollario degli archi sicuri e ADT Union-find

Question 73

ALGORITMO DI KRUSKAL: passi dell'algoritmo

Answer 73

1. si parte da una foresta di alberi ognuno corrispondente a un singolo vertice 2. si ordinano gli archi per peso crescente 3. si itera la selezione di un arco sicuro e lo si aggiunge se i suoi vertici non fanno parte dello stesso albero 4. terminazione quando tutti i vertici sono stati considerati

Question 74

ALGORITMO DI KRUSKAL: complessità

Answer 74

In generale O(|E|log|E|) ma considerando un grafo completo con |E| = |V|^2 allora T(n) = O(|E|log|V|)

Question 75

ALGORITMO DI KRUSKAL: codice della void GRAPHmstK(Graph G);

Answer 75

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

Question 76

A cosa serve l'algoritmo di Kruskal?

Answer 76

Ricerca di un MST

Question 77

A cosa serve l'algoritmo di Prim?

Answer 77

Ricerca di un MST

Question 78

ALGORITMO DI PRIM: su che teorema/corollario si basa?

Answer 78

Teorema degli archi sicuri

Question 79

ALGORITMO DI PRIM: algoritmo soluzione brute-force

Answer 79

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

Question 80

ALGORITMO DI PRIM: algoritmo migliorato

Answer 80

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

Question 81

ALGORITMO DI PRIM: strutture dati utilizzate e loro significato

Answer 81

- 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

Question 82

ALGORITMO DI PRIM: complessità

Answer 82

T(n) = O(|V|^2) per un grafo denso T(n) = O(|E|log|V|)

Question 83

ALGORITMO DI PRIM: codice della void GRAPHmstP(Graph G);

Answer 83

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->V*sizeof(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; } } }

Question 84

CAMMINI MINIMI: su quali grafi si cercano?

Answer 84

Su grafi orientati e pesati

Question 85

CAMMINI MINIMI: definizione di peso di un cammino

Answer 85

w(p) = sum (i = 1, k) w(v_i-1, v_i)

Question 86

CAMMINI MINIMI: definizione di peso di un cammino minimo

Answer 86

È il minimo tra i cammini che connettono s e v, infinito altrimenti

Question 87

CAMMINI MINIMI: definizione di cammino minimo e caratteristiche

Answer 87

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.

Question 88

CAMMINI MINIMI: casistiche in cui ci sono archi con peso negativo

Answer 88

- 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

Question 89

CAMMINI MINIMI: perchè non ha senso che contengano un ciclo?

Answer 89

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

Question 90

CAMMINI MINIMI: caratteristiche dell'approccio brute-force, programmazione dinamica, Greddy

Answer 90

- 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

Question 91

CAMMINI MINIMI: definizione di rilassamento ed esempio

Answer 91

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

Question 92

ALGORITMO DI DIJKSTRA: per cosa lo si usa

Answer 92

Per la ricerca dei cammini minimi su grafi orientati e pesati

Question 93

ALGORITMO DI DIJKSTRA: strategia

Answer 93

Greedy

Question 94

ALGORITMO DI DIJKSTRA: struttura dati

Answer 94

S insieme dei vertici per cui è stato calcolato il cammino minimo V-S vertici. restanti in una PQ

Question 95

ALGORITMO DI DIJKSTRA: algoritmo

Answer 95

1. estrazione dalla coda (V-S) del vertice con distanza minima da S 2. inserimento del vertice in S 3. rilassamento di tutti gli archi uscenti dal vertice fino a quando la coda ha elementi

Question 96

ALGORITMO DI DIJKSTRA: complessità

Answer 96

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

Question 97

ALGORITMO DI DIJKSTRA: codice della void GRAPHspD(Graph G, int id);

Answer 97

void GRAPHspD(Graph G, int id) { int v; link t; PQ pq = PQinit(G->V); int *st, *mindist; st = malloc(G->V*sizeof(int)); mindist = malloc(G->V*sizeof(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); }

Question 98

CAMMINI MINIMI: caso dei DAG

Answer 98

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

Question 99

ALGORITMO DI BELLMAN-FORD: per cosa lo usiamo?

Answer 99

per la ricerca dei cammini minimi nel caso ci siano archi a peso negativo

Question 100

ALGORITMO DI BELLMAN-FORD: strategia

Answer 100

Programmazione dinamica, calcolo bottom-up della soluzione

Question 101

ALGORITMO DI BELLMAN-FORD: soluzione ricorsiva d'ispirazione

Answer 101

- 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

Question 102

ALGORITMO DI BELLMAN-FORD: algoritmo

Answer 102

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

Question 103

ALGORITMO DI BELLMAN-FORD: complessità

Answer 103

T(n) = O(|V||E|)

Question 104

ALGORITMO DI BELLMAN-FORD: codice della void GRAPHspBF(Graph G, int id);

Answer 104

void GRAPHspBF(Graph G, int id){ int v, w, negcycfound; link t; int *st, *mindist; st = malloc(G->V*sizeof(int)); mindist = malloc(G->V*sizeof(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"); }

Question 105

Come viene implementata la PQ per Dijkstra?

Answer 105

Vettore di indici in cui la prio è data dalla mindist