T - Grafi Flashcards

Question 1

Q

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

Answer

A

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

Question 2

Q

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

Answer

A

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

Q

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

Answer

A

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

Q

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

A

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

Q

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

Answer

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

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

Q

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

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

Question 7

Q

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

A

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

Q

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

A

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

Q

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

Answer

A

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

Q

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

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

Question 11

Q

Quali strategie abbiamo studiato per la visita di un grafo?

Answer

A

Depth First Search
Breadth First Search

Question 12

Q

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

Answer

A

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

Question 13

Q

DFS: Cosa si intende con profondità?

Answer

A

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

Question 14

Q

DFS: Come vengono trattati i vertici?

Answer

A

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

Q

DFS: come vengono etichettati gli archi?

Answer

A

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

Q

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

Answer

A

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

Q

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

Answer

A

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

Q

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

Answer

A

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

Question 19

Q

BFS: a che tipo di visita porta

Answer

A

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

Question 20

Q

BFS: cosa calcola di fatto?

Answer

A

Calcola la distanza minima dal vertice di partenza

Question 21

Q

BFS: cosa genera?

Answer

A

Un albero di visita in ampiezza

Question 22

Q

BFS: trattamento vertici

Answer

A

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

Question 23

Q

BFS: quale struttura dati viene utilizzata? Cosa permette?

Answer

A

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

Q

BFS: come vengono visitati i vertici?

Answer

A

In modo parallelo.

Question 25

Q

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

Answer

A

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

Question 26

Q

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

Answer

A

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

Q

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

Answer

A

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

Question 28

Q

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

Answer

A

Quando non si incontrano archi di tipo B in una DFS

Question 29

Q

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

A

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

Q

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

Answer

A

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

Q

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

Answer

A

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

Question 32

Q

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

Answer

A

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

Q

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

Answer

A

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

Q

APPLICAZIONI DEGLI ALGORITMI DI VISITA DEI GRAFI: definizione di ponte

Answer

A

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

Q

DAG: caratteristiche

Answer

A

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

Q

DAG: per cosa viene usato tipicamente?

Answer

A

Viene utilizzato per gli ordinamenti parziali -> problemi di scheduling

Question 37

Q

DAG: quali sono le operazioni tipiche?

Answer

A

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

Q

DAG: quando un ordinamento è unico?

Answer

A

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

Question 39

Q

DAG: struttura dati per l’ordinamento topologico inverso

Answer

A

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

Q

DAG: codice della void DAGrts(Dag D);

Answer

A

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

Q

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

Answer

A

Grafo ordinato con matrice delle adiacenze.

Question 42

Q

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

Answer

A

SI invertono i riferimenti riga-colonna.

Question 43

Q

DAG: codice della void DAGts(Dag D);

Answer

A

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

Question 44

Q

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

Answer

A

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

Question 45

Q

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

Answer

A

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

Q

ALGORITMO DI KOSARAJU: a cosa serve?

Answer

A

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

Question 47

Q

ALGORITMO DI KOSARAJU: concetto

Answer

A

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

Q

ALGORITMO DI KOSARAJU: definizione di grafo trasposto

Answer

A

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

Q

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

Answer

A

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

Q

ALGORITMO DI KOSARAJU: struttura dati per la ricerca delle SCC

Answer

A

*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

Q

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

Answer

A

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

Q

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

Answer

A

Grafi non orientati, pesati, connessi

Question 53

Q

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

Answer

A

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

Q

ALBERI RICOPRENTI MINIMI: sigla inglese

Answer

A

Minimum Weight Spanning Tree MST

Question 55

Q

ALBERI RICOPRENTI MINIMI:
se un grafo è “____” allora è un albero

Answer

A

aciclico e copre tutti i vertici

Question 56

Q

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

Answer

A

quando i pesi degli archi sono tutti distinti

Question 57

Q

ALBERI RICOPRENTI MINIMI: possibili rappresentazioni dell’albero MST

Answer

A

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

Q

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

Answer

A

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

Question 59

Q

ALBERI RICOPRENTI MINIMI: quando un arco è sicuro?

Answer

A

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

Question 60

Q

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

Answer

A

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

Q

ALBERI RICOPRENTI MINIMI: definizione di arco leggero

Answer

A

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

Question 62

Q

ALBERI RICOPRENTI MINIMI: Teorema degli archi sicuri

Answer

A

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

Q

ALBERI RICOPRENTI MINIMI: Corollario degli archi sicuri

Answer

A

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

Q

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

Answer

A

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

Answer 65

A

UFfind e UFunion

Answer 66

A

UF.c
static int *id, *sz;

Answer 67

A

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

Answer 68

A

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

Answer 69

A

O(1): assegnazione

Answer 70

A

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

Answer 71

A

Kruskal e Prim

Answer 72

A

Corollario degli archi sicuri e ADT Union-find

Answer 73

A

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

Answer 74

A

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

Answer 75

A

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

Answer 76

A

Ricerca di un MST

Answer 77

A

Ricerca di un MST

Answer 78

A

Teorema degli archi sicuri

Answer 79

A

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

Answer 80

A

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

Answer 81

A

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

Answer 82

A

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

Answer 83

A

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

Answer 84

A

Su grafi orientati e pesati

Answer 85

A

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

Answer 86

A

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

Answer 87

A

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.

Answer 88

A

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

Answer 89

A

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

Answer 90

A

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

Answer 91

A

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

Answer 92

A

Per la ricerca dei cammini minimi su grafi orientati e pesati

Answer 93

A

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

Answer 94

A

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

Answer 95

A

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

Answer 96

A

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

Answer 97

A

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

Answer 98

A

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

Answer 99

A

Programmazione dinamica, calcolo bottom-up della soluzione

Answer 100

A

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

Answer 101

A

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

Answer 102

A

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

Answer 103

A

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

Answer 104

A

Vettore di indici in cui la prio è data dalla mindist

Brainscape's Knowledge GenomeTM

T - Grafi Flashcards

Brainscape's Knowledge Genome^TM