esercizi sulle liste e sui grafi

Esercizi su liste e grafi
Marco Liverani∗
Gennaio 2011
∗ E-mail: [email protected] – Web: http://www.mat.uniroma3.it/users/liverani
1
1 Esercizi sulle liste
Esercizio 1 Letta in input una sequenza di numeri interi positivi memorizzarla in una
lista. Costruire una seconda lista contenente soltanto gli elementi della prima lista che
non siano numeri primi. Stampare la seconda lista.
1
2
3
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
int primo(int x) {
int i, flag;
flag = 1;
i = 2;
while (i<=sqrt(x) && flag==1) {
if (x%i == 0)
flag = 0;
i = i+1;
}
return(flag);
}
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
primo = NULL;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("inserisci %d numeri interi positivi: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
37
38
39
40
41
42
43
44
45
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d ", p->info);
p = p->next;
}
printf("\n");
return;
}
46
47
48
int main(void) {
struct nodo *p, *q, *r;
2
p = leggi_lista();
r = NULL;
while (p != NULL) {
if (primo(p->info) == 0) {
q = malloc(sizeof(struct nodo));
q->info = p->info;
q->next = r;
r = q;
}
p = p->next;
}
stampa_lista(r);
return(0);
49
50
51
52
53
54
55
56
57
58
59
60
61
62
}
3
Esercizio 2 Letta in input una lista, costruire una seconda lista con gli elementi disposti
al contrario rispetto alla lista originale (es.: se la lista letta in input è 1 → 8 → 4 viene
costruita la lista 4 → 8 → 1). Stampare la seconda lista.
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
struct nodo {
int info;
struct nodo *next;
};
struct nodo *leggi_lista(void) {
struct nodo *p, *primo=NULL;
int i, n;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d numeri: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("NULL\n");
return;
}
struct nodo *inverti(struct nodo *p) {
struct nodo *q, *q1 = NULL;
while (p != NULL) {
q = malloc(sizeof(struct nodo));
q->info = p->info;
q->next = q1;
q1 = q;
p = p->next;
}
return(q1);
}
int main(void) {
struct nodo *p, *q;
p = leggi_lista();
q = inverti(p);
stampa_lista(q);
return(0);
}
4
Esercizio 3 Lette in input due liste di numeri interi ognuna delle quali ordinata, costruire
una terza lista di numeri interi ordinata, ottenuta mediante la “fusione” delle prime due.
Stampare la lista.
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
struct nodo {
int info;
struct nodo *next;
};
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct nodo *fusione(struct nodo *p1, struct nodo *p2) {
struct nodo *p, *primo = NULL;
while (p1 != NULL && p2 != NULL) {
p = malloc(sizeof(struct nodo));
p->next = primo;
primo = p;
if (p1->info > p2->info) {
p->info = p1->info;
p1 = p1->next;
} else {
p->info = p2->info;
p2 = p2->next;
}
}
while (p1 != NULL) {
p = malloc(sizeof(struct nodo));
p->info = p1->info;
p->next = primo;
primo = p;
p1 = p1->next;
}
while (p2 != NULL) {
p = malloc(sizeof(struct nodo));
p->info = p2->info;
p->next = primo;
primo = p;
p2 = p2->next;
}
return(primo);
}
39
40
41
42
43
44
45
46
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("NULL\n");
}
47
48
49
50
struct nodo *leggi_lista(void) {
struct nodo *p, *primo=NULL;
int i, n;
5
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d numeri: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
51
52
53
54
55
56
57
58
59
60
61
}
62
63
64
65
66
67
68
69
70
int main(void) {
struct nodo *p, *q, *r;
p = leggi_lista();
q = leggi_lista();
r = fusione(p, q);
stampa_lista(r);
return(0);
}
6
Esercizio 4 Letta in input una lista di numeri interi stamparla e poi ordinarla utilizzando l’algoritmo S ELECTION S ORT. Stampare la lista ordinata.
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
struct nodo {
int info;
struct nodo *next;
};
8
9
10
11
12
13
14
15
void scambia(int *a, int *b) {
int c;
c = *a;
*a = *b;
*b = c;
return;
}
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void selection_sort(struct nodo *p) {
struct nodo *q;
while (p != NULL) {
q = p->next;
while (q != NULL) {
if (p->info > q->info)
scambia(&p->info, &q->info);
q = q->next;
}
p = p->next;
}
return;
}
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
struct nodo *leggi_lista(void) {
struct nodo *p, *primo=NULL;
int i, n;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d numeri: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
45
46
47
48
49
50
51
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("NULL\n");
7
52
}
53
54
55
56
57
58
59
60
61
int main(void) {
struct nodo *p;
p = leggi_lista();
stampa_lista(p);
selection_sort(p);
stampa_lista(p);
return(0);
}
8
Esercizio 5 Leggere in input una sequenza di n numeri floating point e rappresentarla con una lista L; stampare la lista. Costruire una seconda lista L 0 composta dai soli
elementi di L maggiori della media; stampare L 0 .
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
struct nodo {
float info;
struct nodo *next;
};
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
printf(" inserisci il numero di elementi: ");
scanf("%d", &n);
printf(" inserisci %d elementi: ", n);
primo = NULL;
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
p->next = primo;
scanf("%f", &p->info);
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%3.2f --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
}
33
34
35
36
37
38
39
40
41
42
float media(struct nodo *p) {
float s=0.0, n=0.0;
while (p != NULL) {
s = s + p->info;
n = n + 1;
p = p->next;
}
return(s/n);
}
43
44
45
46
47
48
49
50
int main(void) {
struct nodo *p, *q, *r, *s;
float m;
p = leggi_lista();
stampa_lista(p);
m = media(p);
r = NULL;
9
q = p;
while (q != NULL) {
if (q->info > m) {
s = malloc(sizeof(struct nodo));
s->info = q->info;
s->next = r;
r = s;
}
q = q->next;
}
stampa_lista(r);
return(0);
51
52
53
54
55
56
57
58
59
60
61
62
63
}
10
Esercizio 6 Leggere in input una sequenza di numeri interi ordinati in ordine crescente.
Dopo aver memorizzato la sequenza in una lista, inserire nella posizione corretta all’interno della lista, tutti i numeri mancanti. Stampare in output la lista. Non devono essere
usate altre liste o array di appoggio.
Esempio Supponiamo che sia fornita in input la sequenza 4, 7, 8, 9, 15, 17, 21. Dopo
aver memorizzato gli elementi nella lista 4 → 7 → 8 → . . . → 21, vengono inseriti i numeri mancanti, ottenendo la lista composta dagli elementi 4 → 5 → 6 → 7 → 8 → . . . →
19 → 20 → 21.
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
struct nodo {
int info;
struct nodo *next;
};
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
struct nodo *leggi_lista(void) {
struct nodo *p, *primo = NULL;
int i, n;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d numeri interi in ordine crescente: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void completa_lista(struct nodo *p) {
struct nodo *q;
while (p->next != NULL) {
if (p->info > p->next->info + 1) {
q = malloc(sizeof(struct nodo));
q->info = p->next->info + 1;
q->next = p->next;
p->next = q;
} else
p = p->next;
}
return;
}
37
38
39
40
41
42
43
44
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
11
45
}
46
47
48
49
50
51
52
53
int main(void) {
struct nodo *primo;
primo = leggi_lista();
completa_lista(primo);
stampa_lista(primo);
return(0);
}
12
2 Esercizi sui grafi
Esercizio 7 Letto in input un grafo G orientato, rappresentarlo con liste di adiacenza.
Costruire e stampare le liste di adiacenza del grafo H opposto di G: V (H ) = V (G), E (H ) =
{(u, v) : u, v ∈ V (H ) e (v, u) ∈ E (G)} (il grafo con il verso degli spigoli invertito).
1
2
3
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
struct nodo *p, *primo = NULL;
int i, n;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d vertici: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d ---> ", p->info);
p = p->next;
}
printf("NULL\n");
return;
}
33
34
35
36
37
38
39
40
41
42
43
int leggi_grafo(struct nodo *L[]) {
int i, n;
printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista dei vertici adiacenti al vertice %d.\n", i);
L[i] = leggi_lista();
}
return(n);
}
44
45
46
47
48
void stampa_grafo(struct nodo *L[], int n) {
int i;
for (i=0; i<n; i++) {
printf("%2d: ", i);
13
stampa_lista(L[i]);
}
printf("\n");
return;
49
50
51
52
53
}
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
void opposto(struct nodo *G[], struct nodo *H[], int n) {
int i;
struct nodo *p, *q;
for (i=0; i<n; i++) {
H[i] = NULL;
}
for (i=0; i<n; i++) {
p = G[i];
while (p != NULL) {
q = malloc(sizeof(struct nodo));
q->info = i;
q->next = H[p->info];
H[p->info] = q;
p = p->next;
}
}
return;
}
73
74
75
76
77
78
79
80
81
82
int main(void) {
struct nodo *G[MAX], *H[MAX];
int n;
n = leggi_grafo(G);
stampa_grafo(G, n);
opposto(G, H, n);
stampa_grafo(H, n);
return(0);
}
14
Esercizio 8 Letto in input un grafo G = (V, E ) non orientato, costruire il grafo H = (V, E 0 )
complementare, tale che (u, v) ∈ E ⇐⇒ (u, v) ∉ E 0 .
1
2
3
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
struct nodo *p, *primo = NULL;
int i, n;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d vertici: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d ---> ", p->info);
p = p->next;
}
printf("NULL\n");
return;
}
33
34
35
36
37
38
39
40
41
42
43
int leggi_grafo(struct nodo *L[]) {
int i, n;
printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista dei vertici adiacenti al vertice %d.\n", i);
L[i] = leggi_lista();
}
return(n);
}
44
45
46
47
48
49
50
51
void stampa_grafo(struct nodo *L[], int n) {
int i;
for (i=0; i<n; i++) {
printf("%2d: ", i);
stampa_lista(L[i]);
}
printf("\n");
15
return;
52
53
}
54
55
56
57
58
59
60
61
62
63
64
65
int adiacente(struct nodo *G[], int u, int v) {
struct nodo *p;
p = G[u];
while (p != NULL && p->info != v) {
p = p->next;
}
if (p == NULL)
return(0);
else
return(1);
}
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
void complementare(struct nodo *G[], struct nodo *H[], int n) {
int i, j;
struct nodo *p;
for (i=0; i<n; i++) {
H[i] = NULL;
}
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
if (i != j && !adiacente(G, i, j)) {
p = malloc(sizeof(struct nodo));
p->info = j;
p->next = H[i];
H[i] = p;
}
}
}
return;
}
85
86
87
88
89
90
91
92
93
94
int main(void) {
struct nodo *G[MAX], *H[MAX];
int n;
n = leggi_grafo(G);
stampa_grafo(G, n);
complementare(G, H, n);
stampa_grafo(H, n);
return(0);
}
16
Esercizio 9 Letti in input due interi n e k (0 < k < n), costruire un grafo G = (V, E ) in
modo casuale tale che V = {0, 1, 2, . . . , n − 1} e ogni vertice abbia al massimo k spigoli
uscenti.
1
2
3
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d ---> ", p->info);
p = p->next;
}
printf("NULL\n");
return;
}
18
19
20
21
22
23
24
25
26
27
28
void stampa_grafo(struct nodo *L[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf("%2d: ", i);
stampa_lista(L[i]);
}
printf("\n");
return;
}
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
void crea_grafo(struct nodo *G[], int n, int k) {
struct nodo *p;
int i, j, x;
srand((unsigned)time(NULL));
for (i=0; i<n; i++) {
G[i] = NULL;
for (j=0; j<k; j++) {
x = rand() % n;
if (x != i) {
p = G[i];
while (p != NULL && p->info != x) {
p = p->next;
}
if (p == NULL) {
p = malloc(sizeof(struct nodo));
p->info = x;
p->next = G[i];
G[i] = p;
}
}
}
17
}
return;
51
52
53
}
54
55
56
57
58
59
60
61
62
63
64
65
int main(void) {
struct nodo *G[100];
int n, k;
printf("Numero di vertici: ");
scanf("%d", &n);
printf("Grado uscente massimo: ");
scanf("%d", &k);
crea_grafo(G, n, k);
stampa_grafo(G, n);
return(0);
}
18
Esercizio 10 Letto in input un grafo non orientato G = (V, E ) con n vertici (V = {0, 1, . . . , n−
1}) e una lista di numeri interi compresi tra 0 e n − 1, verificare se la lista rappresenta un
cammino sul grafo.
1
2
3
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
primo = NULL;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d vertici: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
25
26
27
28
29
30
31
32
33
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d ---> ", p->info);
p = p->next;
}
printf("NULL\n");
return;
}
34
35
36
37
38
39
40
41
42
43
44
int leggi_grafo(struct nodo *L[]) {
int i, n;
printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista dei vertici adiacenti al vertice %d.\n", i);
L[i] = leggi_lista();
}
return(n);
}
45
46
47
48
49
50
void stampa_grafo(struct nodo *L[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf("%2d: ", i);
19
stampa_lista(L[i]);
}
printf("\n");
return;
51
52
53
54
55
}
56
57
58
59
60
61
62
63
64
65
66
67
int adiacente(struct nodo *G[], int u, int v) {
struct nodo *p;
p = G[u];
while (p != NULL && p->info != v) {
p = p->next;
}
if (p == NULL)
return(0);
else
return(1);
}
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
int main(void) {
struct nodo *G[100], *primo, *p;
int n, ok=1;
n = leggi_grafo(G);
stampa_grafo(G, n);
printf("Inserimento della lista di vertici da verificare\n");
primo = leggi_lista();
p = primo;
while (ok && p->next != NULL) {
if (!adiacente(G, p->info, p->next->info))
ok = 0;
p = p->next;
}
if (ok)
printf("La lista costituisce un cammino sul grafo.\n");
else
printf("La lista non rappresenta un cammino sul grafo.\n");
return(1);
}
20
Esercizio 11 Leggere in input k liste di numeri interi e costruire un grafo non orientato
G = (V, E ) per cui le k liste rappresentino dei cammini.
1
2
3
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
primo = NULL;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d vertici: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
25
26
27
28
29
30
31
32
33
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d ---> ", p->info);
p = p->next;
}
printf("NULL\n");
return;
}
34
35
36
37
38
39
40
41
42
43
44
int leggi_grafo(struct nodo *L[]) {
int i, n;
printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista dei vertici adiacenti al vertice %d.\n", i);
L[i] = leggi_lista();
}
return(n);
}
45
46
47
48
49
50
51
void stampa_grafo(struct nodo *L[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf("%2d: ", i);
stampa_lista(L[i]);
21
}
printf("\n");
return;
52
53
54
55
}
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
int main(void) {
struct nodo *L[100], *G[100], *p, *q;
int i, n=0, k;
for (i=0; i<100; i++)
G[i] = NULL;
printf("Quante liste vuoi inserire? ");
scanf("%d", &k);
for (i=0; i<k; i++)
L[i] = leggi_lista();
for (i=0; i<k; i++) {
p = L[i];
if (n < p->info)
n = p->info;
while (p->next != NULL) {
if (n < p->next->info)
n = p->next->info;
q = G[p->info];
while (q != NULL && q->info != p->next->info) {
q = q->next;
}
if (q == NULL) {
q = malloc(sizeof(struct nodo));
q->info = p->next->info;
q->next = G[p->info];
G[p->info] = q;
}
p = p->next;
}
}
stampa_grafo(G, n+1);
return(0);
}
22
Esercizio 12 Leggere in input un grafo orientato G = (V, E ) e rappresentarlo mediante
liste di adiacenza. Stampare le liste di adiacenza del grafo. Letto in input un vertice v ∈
V (G) (0 ≤ v ≤ n) stampare tutti i vertici u ∈ V (G) a cui v è adiacente (tutti i vertici u tali
che (u, v) ∈ E (G)).
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
struct nodo {
int info;
struct nodo *next;
};
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
printf(" inserisci il numero di elementi: ");
scanf("%d", &n);
printf(" inserisci %d elementi: ", n);
primo = NULL;
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
p->next = primo;
scanf("%d", &p->info);
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
}
33
34
35
36
37
38
39
40
41
42
43
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("Inserisci il numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d:\n", i);
G[i] = leggi_lista();
}
return(n);
}
44
45
46
47
48
49
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf(" vertici adiacenti a %d: ", i);
23
stampa_lista(G[i]);
}
return;
50
51
52
53
}
54
55
56
57
58
59
60
61
62
63
64
65
66
int adiacente(int a, int b, struct nodo *G[]) {
struct nodo *p;
int r;
p = G[a];
while (p != NULL && p->info != b)
p = p->next;
if (p == NULL)
r = 0;
else
r = 1;
return(r);
}
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
int main(void) {
struct nodo *L[20];
int n, u, v;
n = leggi_grafo(L);
stampa_grafo(L, n);
printf("Inserisci un vertice del grafo: ");
scanf("%d", &v);
printf("Vertici a cui %d e’ adiacente: ", v);
for (u=0; u<n; u++)
if (adiacente(u, v, L))
printf("%d ", u);
printf("\n");
return(0);
}
24
Esercizio 13 Leggere in input un grafo orientato G = (V, E ) e rappresentarlo mediante
liste di adiacenza. Stampare le liste di adiacenza del grafo. Letto in input un vertice v
(0 ≤ v ≤ n) eliminare tutti gli spigoli entranti in v. Stampare le liste di adiacenza del
grafo.
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
struct nodo {
int info;
struct nodo *next;
};
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
printf(" inserisci il numero di elementi: ");
scanf("%d", &n);
printf(" inserisci %d elementi: ", n);
primo = NULL;
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
p->next = primo;
scanf("%d", &p->info);
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
}
33
34
35
36
37
38
39
40
41
42
43
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("Inserisci il numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d:\n", i);
G[i] = leggi_lista();
}
return(n);
}
44
45
46
47
48
49
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf(" vertici adiacenti a %d: ", i);
25
stampa_lista(G[i]);
}
return;
50
51
52
53
}
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
void elimina_spigoli(struct nodo *G[], int n, int v) {
int i;
struct nodo *p, *prec;
for (i=0; i<n; i++) {
p = G[i];
prec = NULL;
while (p != NULL && p->info != v) {
prec = p;
p = p->next;
}
if (p != NULL) {
if (prec == NULL) {
G[i] = p->next;
free(p);
} else {
prec->next = p->next;
free(p);
}
}
}
return;
}
77
78
79
80
81
82
83
84
85
86
87
88
int main(void) {
struct nodo *L[20];
int n, v;
n = leggi_grafo(L);
stampa_grafo(L, n);
printf("Inserisci un vertice del grafo: ");
scanf("%d", &v);
elimina_spigoli(L, n, v);
stampa_grafo(L, n);
return(0);
}
26
Esercizio 14 Letto un grafo non orientato G = (V, E ) e letta una lista di vertici di V ,
L = {v 1 , . . . , v k }, stabilire se il sottografo G 0 indotto da L è completo. Un sottografo è completo se i suoi vertici sono adiacenti a tutti gli altri vertici del sottografo. Il grafo G 0 è il
sottografo indotto di G mediante l’insieme di vertici L ⊆ V (G) se gli spigoli di G 0 sono tutti
e soli gli spigoli di G aventi per estremi vertici in L.
1
2
3
#include <stdlib.h>
#include <stdio.h>
#define MAX 100
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
struct nodo *p, *primo = NULL;
int i, n;
printf(" inserisci il numero di elementi: ");
scanf("%d", &n);
printf(" inserisci %d elementi: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
p->next = primo;
scanf("%d", &p->info);
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
}
33
34
35
36
37
38
39
40
41
42
43
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("Inserisci il numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d:\n", i);
G[i] = leggi_lista();
}
return(n);
}
44
45
46
47
48
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
27
printf(" vertici adiacenti a %d: ", i);
stampa_lista(G[i]);
49
50
}
return;
51
52
53
}
54
55
56
57
58
59
60
61
62
63
64
65
int adiacente(int i, int j, struct nodo *G[]) {
struct nodo *p;
p = G[i];
while (p != NULL && p->info != j) {
p = p->next;
}
if (p == NULL)
return(0);
else
return(1);
}
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
int completo(struct nodo *G[], struct nodo *L, int n) {
struct nodo *p, *q;
int flag=1;
p = L;
while (p != NULL && flag==1) {
q = L;
while (q != NULL && flag==1) {
if (q->info != p->info && !adiacente(p->info, q->info, G))
flag = 0;
q = q->next;
}
p = p->next;
}
return(flag);
}
82
83
84
85
86
87
88
89
90
91
92
93
94
95
int main(void) {
struct nodo *G[MAX], *L;
int n;
n = leggi_grafo(G);
stampa_grafo(G, n);
L = leggi_lista();
if (completo(G, L, n)) {
printf("Il sottografo di G indotto da L e‘ completo.\n");
} else {
printf("Il sottografo di G indotto da L NON e‘ completo.\n");
}
return(0);
}
28
Esercizio 15 Letto un grafo non orientato G = (V, E ) rappresentarlo con liste di adiacenza. Letta in input un sottoinsieme di vertici di V , rappresentarla mediante una lista L
(L ⊆ V ). Verificare se L è una copertura di vertici di G, ossia se per ogni (u, v) ∈ E risulta
u ∈ L o v ∈ L (o entrambi).
Esempio Consideriamo il grafo G = (V, E ) rappresentato in figura, in cui l’insieme dei
vertici è V = {0, 1, 2, 3, 4} e l’insieme degli spigoli è E = {(0, 1), (0, 2), (1, 2), (2, 3), (2, 4), (3, 4)}:
s1
Q
Q
0
s
Q
Q
Qs2
4
s
s
3
La lista L = {1, 2, 3} è una copertura di G, mentre L 0 = {0, 1, 3} non è una copertura,
infatti gli estremi dello spigolo (4, 2) non appartengono a L 0 .
1
2
3
#include <stdlib.h>
#include <stdio.h>
#define MAX 20
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
int i, n;
struct nodo *p, *primo=NULL;
printf("Numero di elementi: ");
scanf("%d", &n);
printf("Inserisci %d elementi: ", n);
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
scanf("%d", &p->info);
p->next = primo;
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("NULL\n");
return;
}
33
29
34
35
36
37
38
39
40
41
42
43
int leggi_grafo(struct nodo *v[]) {
int i, n;
printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d\n", i);
v[i] = leggi_lista();
}
return(n);
}
44
45
46
47
48
49
50
51
52
53
void stampa_grafo(struct nodo *v[], int n) {
int i;
printf("Liste di adiacenza del grafo\n");
for (i=0; i<n; i++) {
printf("%d: ", i);
stampa_lista(v[i]);
}
return;
}
54
55
56
57
58
59
60
61
62
63
int appartiene(int i, struct nodo *t) {
int trovato = 0;
while (t!=NULL && !trovato) {
if (t->info == i)
trovato = 1;
t = t->next;
}
return(trovato);
}
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
int copertura(struct nodo *v[], int n, struct nodo *p) {
struct nodo *q;
int i, flag=1;
for (i=0; i<n && flag; i++) {
flag = 0;
if (!appartiene(i, p)) {
q = v[i];
flag = 1;
while (flag && q!=NULL) {
if (!appartiene(q->info, p))
flag = 0;
q = q->next;
}
} else
flag = 1;
}
return(flag);
}
83
84
85
86
87
int main(void) {
struct nodo *v[MAX], *p;
int n;
n = leggi_grafo(v);
30
p = leggi_lista();
if (copertura(v, n, p))
printf("La lista e‘ una copertura del grafo.\n");
else
printf("La lista non e‘ una copertura del grafo.\n");
return(0);
88
89
90
91
92
93
94
}
31
Esercizio 16 Letto in input un grafo G = (V, E ) non orientato, costruire e stampare un
grafo G 0 = (V, E 0 ) orientato, tale che (u, v) ∈ E 0 se e solo se g (u) > g (v), dove con g (v) si
è indicato il grado del vertice v (il numero di spigoli entranti o uscenti: in un grafo non
orientato non c’è distinzione).
1
2
#include <stdlib.h>
#include <stdio.h>
3
4
5
6
7
struct nodo {
int info;
struct nodo *next;
};
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
printf(" inserisci il numero di elementi: ");
scanf("%d", &n);
printf(" inserisci %d elementi: ", n);
primo = NULL;
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
p->next = primo;
scanf("%d", &p->info);
primo = p;
}
return(primo);
}
24
25
26
27
28
29
30
31
32
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
}
33
34
35
36
37
38
39
40
41
42
43
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("Inserisci il numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d:\n", i);
G[i] = leggi_lista();
}
return(n);
}
44
45
46
47
48
49
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf(" vertici adiacenti a %d: ", i);
32
stampa_lista(G[i]);
}
return;
50
51
52
53
}
54
55
56
57
58
59
60
61
62
int grado(struct nodo *p) {
int cont = 0;
while (p!=NULL) {
cont ++;
p = p->next;
}
return(cont);
}
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
void costruisci_grafo(struct nodo *G[], struct nodo *G1[], int n) {
int i, gi;
struct nodo *p, *q;
for (i=0; i<n; i++) {
gi = grado(G[i]);
p = G[i];
G1[i] = NULL;
while (p != NULL) {
if (gi > grado(G[p->info])) {
q = malloc(sizeof(struct nodo));
q->info = p->info;
q->next = G1[i];
G1[i] = q;
}
p = p->next;
}
}
return;
}
83
84
85
86
87
88
89
90
91
92
int main(void) {
struct nodo *G[100], *G1[100];
int n;
n = leggi_grafo(G);
stampa_grafo(G, n);
costruisci_grafo(G, G1, n);
stampa_grafo(G1, n);
return(0);
}
33
Esercizio 17 Leggere in input un grafo G = (V, E ) non orientato e memorizzarlo mediante
liste di adiacenza. Scelto arbitrariamente uno dei vertici v ∈ V di grado massimo, eliminare dal grafo tutti gli spigoli (u, w) ∈ E per ogni u e w adiacenti a v. Stampare le liste di
adiacenza del grafo così modificato.
Esempio Sia G = (V, E ) il grafo letto in input rappresentato in figura (a sinistra), con
V = {1, 2, 3, 4, 5, 6} ed E = {(1, 2), (2, 3), (3, 4), (4, 5), (5, 6), (6, 1), (1, 5), (2, 5), (2, 4)}. I vertici di
grado massimo sono 2 e 5 (entrambi di grado 4). Scegliendo il vertice 5, devono essere
eliminati gli spigoli (1, 2) (perché 1, 2 ∈ N (5)), (1, 6) (perché 1, 6 ∈ N (5)) e (2, 4) (perché
4, 2 ∈ N (5)). si ottiene così il grafo rappresentato a destra nella figura.
u
@
@
2
u
@
@
1
6
1
2
3
@
@
@u
h
5
2
u
1
@
@
u
u
@
@
3
u
@
@
@
@u
u
4
6
@
@
@u
h
#include <stdlib.h>
#include <stdio.h>
#define MAX 30
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
printf(" inserisci il numero di elementi: ");
scanf("%d", &n);
printf(" inserisci %d elementi: ", n);
primo = NULL;
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
p->next = primo;
scanf("%d", &p->info);
primo = p;
}
return(primo);
}
25
26
27
28
29
30
31
32
33
5
u
4
4
5
3
u
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
}
34
34
35
36
37
38
39
40
41
42
43
44
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("Inserisci il numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d:\n", i);
G[i] = leggi_lista();
}
return(n);
}
45
46
47
48
49
50
51
52
53
54
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf(" vertici adiacenti a %d: ", i);
stampa_lista(G[i]);
}
return;
}
55
56
57
58
59
60
61
62
63
int grado(struct nodo *p) {
int cont = 0;
while (p!=NULL) {
cont ++;
p = p->next;
}
return(cont);
}
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
struct nodo *elimina(int v, struct nodo *primo) {
struct nodo *p, *q = NULL;
if (primo != NULL) {
if (primo->info == v) {
q = primo;
primo = primo->next;
} else {
p = primo;
while (p->next != NULL && p->next->info != v) {
p = p->next;
}
if (p->next != NULL) {
q = p->next;
p->next = p->next->next;
}
}
if (q != NULL)
free(q);
}
return(primo);
}
86
87
88
int main(void) {
35
struct nodo *G[MAX], *p, *q;
int n, gmax, vmax, v, g;
n = leggi_grafo(G);
gmax = grado(G[0]);
vmax = 0;
for (v=1; v<n; v++) {
g = grado(G[v]);
if (g > gmax) {
gmax = g;
vmax = v;
}
}
printf("Il vertice di grado massimo scelto e’ %d.\n", vmax);
p = G[vmax];
while (p->next != NULL) {
q = p->next;
while (q != NULL) {
G[q->info] = elimina(p->info, G[q->info]);
G[p->info] = elimina(q->info, G[p->info]);
q = q->next;
}
p = p->next;
}
stampa_grafo(G, n);
return(0);
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
}
36
Esercizio 18 Leggere in input un grafo orientato G = (V, E ) e rappresentarlo mediante
liste di adiacenza. Leggere in input un insieme di pesi (interi) associati ai vertici del grafo:
{w 1 , ..., w n }. Modificando le liste di adiacenza con cui è stato rappresentato il grafo G,
variare l’orientamento degli spigoli in modo tale che per ogni spigolo (u, v) risulti w u ≤
wv .
Esempio Sia G = (V, E ) il grafo orientato letto in input rappresentato in figura, con
V = {1, 2, 3, 4, 5} ed E = {(1, 2), (2, 4), (3, 2), (4, 2), (4, 3), (4, 5), (5, 1), (5, 2)}. Sia W l’insieme
dei pesi associati ai vertici del grafo: W = {10, 30, 5, 17, 23}. Sulla sinistra è rappresentato il grafo letto in input e sulla destra il grafo prodotto dalla rielaborazione richiesta
dall’esercizio.
1(10)
u
6
1
2
3
1(10)
u
- 2(20)
u
I
@
6
@
@u
3(5)
- 2(20)
u
I
@
6
@
@u
3(5)
u
?
u
?
u
u
5(23)
4(17)
5(23)
4(17)
#include <stdlib.h>
#include <stdio.h>
#define MAX 50
4
5
6
7
8
struct nodo {
int info;
struct nodo *next;
};
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
struct nodo *leggi_lista(void) {
struct nodo *p, *primo;
int i, n;
printf(" inserisci il numero di elementi: ");
scanf("%d", &n);
printf(" inserisci %d elementi: ", n);
primo = NULL;
for (i=0; i<n; i++) {
p = malloc(sizeof(struct nodo));
p->next = primo;
scanf("%d", &p->info);
primo = p;
}
return(primo);
}
25
26
27
28
29
30
31
32
33
void stampa_lista(struct nodo *p) {
while (p != NULL) {
printf("%d --> ", p->info);
p = p->next;
}
printf("Null\n");
return;
}
37
34
35
36
37
38
39
40
41
42
43
44
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("Inserisci il numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d:\n", i);
G[i] = leggi_lista();
}
return(n);
}
45
46
47
48
49
50
51
52
53
54
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("Liste di adiacenza dei vertici del grafo:\n");
for (i=0; i<n; i++) {
printf(" vertici adiacenti a %d: ", i);
stampa_lista(G[i]);
}
return;
}
55
56
57
58
59
60
61
62
63
64
void leggi_pesi(int w[], int n) {
int i;
printf("Inserisci i pesi assegnati ai vertici del grafo:\n");
for (i=0; i<n; i++) {
printf(" w(%d) = ", i);
scanf("%d", &w[i]);
}
return;
}
65
66
67
68
69
70
71
72
73
74
75
76
77
78
void aggiungi(struct nodo *G[], int i, int j) {
struct nodo *p;
p = G[i];
while (p != NULL && p->info != j)
p = p->next;
if (p == NULL) {
p = malloc(sizeof(struct nodo));
p->info = j;
p->next = G[i];
G[i] = p;
}
return;
}
79
80
81
82
83
84
85
86
87
int main(void) {
struct nodo *G[MAX], *p, *prec;
int i, n, w[MAX];
n = leggi_grafo(G);
leggi_pesi(w, n);
for (i=0; i<n; i++) {
p = G[i];
prec = NULL;
38
while (p != NULL) {
if (w[i] > w[p->info]) {
aggiungi(G, p->info, i);
if (prec != NULL) {
prec->next = p->next;
free(p);
p = prec->next;
} else {
G[i] = p->next;
free(p);
p = G[i];
}
} else {
prec = p;
p = p->next;
}
}
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
}
stampa_grafo(G, n);
return(0);
105
106
107
108
}
39