Gli esercizi
Testi e soluzioni di alcuni esercizi
Eliminazione di un vertice
/*
** elimina_vertice.c
**
** Dato un grafo orientato G=(V,E) lo si rappresenti mediante
** una matrice di adiacenza. Dato un vertice v verificare che
** v abbia in G un unico predecessore. In tal caso costruire
** il grafo G' ottenuto da G eliminando v e collegando il
** predecessore di v a tutti i successori di v.
**
** Marco Liverani (liverani@mat.uniroma3.it) - Febbraio 1999
*/
#include <stdlib.h>
#include <stdio.h>
#define MAX 50
struct nodo {
int info;
struct nodo *next;
};
/*
** leggi_grafo
**
** per ogni vertice v di G legge i vertici u adiacenti
** e pone m[v][u] = 1. Restituisce il numero di vertici di G.
*/
int leggi_grafo(int *m) {
int i, j, n;
printf("Numero di vertici: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
for (j=0; j<n; j++) {
*(m+i*MAX+j) = 0;
}
}
for (i=0; i<n; i++) {
printf("Vertici adiacenti a %d (-1 per terminare): ", i);
scanf("%d", &j);
while (j != -1) {
*(m+i*MAX+j) = 1;
scanf("%d", &j);
}
}
return(n);
}
/*
** stampa_grafo
**
** stampa le liste di adiacenza di G.
*/
void stampa_grafo(struct nodo **l, int n) {
int i;
struct nodo *p;
for (i=0; i<n; i++) {
p = *(l+i);
printf("%d: ", i);
while (p != NULL) {
printf("%d -> ", p->info);
p = p->next;
}
printf("NULL\n");
}
return;
}
/*
** verifica
**
** per ogni vertice i di G diverso da v verifica se
** esiste uno spigolo (i,v) entrante in v e conta il
** numero di predecessori di v. Se v ha un unico
** predecessore restituisce il numero di tale vertice,
** altrimenti restituisce -1.
*/
int verifica(int *m, int n, int v) {
int i, predecessore, npred;
npred = 0;
predecessore = -1;
for (i=0; i<n; i++) {
if (i != v && *(m+i*MAX+v) == 1) {
predecessore = i;
npred++;
}
}
if (npred == 1)
return(predecessore);
else
return(-1);
}
/*
** elimina_vertice
**
** elimina dal grafo il vertice v, collegando il predecessore
** di v a tutti i vertici di G successori di v.
*/
void elimina_vertice(int predecessore, int v, int *m, int n) {
int i;
for (i=0; i<n; i++) {
if (*(m + v*MAX + i) == 1) {
*(m + predecessore*MAX + i) = 1;
*(m + v*MAX + i) = 0;
}
}
*(m + predecessore*MAX + v) = 0;
return;
}
/*
** nuovo_grafo;
**
** costruisce le liste di adiacenza del grafo G, privato
** del vertice v.
*/
void nuovo_grafo(int *m, struct nodo **l, int n) {
int i, j;
struct nodo *p;
for (i=0; i<n; i++) {
*(l+i) = NULL;
for (j=0; j<n; j++) {
if (*(m + i*MAX + j) == 1) {
p = malloc(sizeof(struct nodo));
p->info = j;
p->next = *(l+i);
*(l+i) = p;
}
}
}
return;
}
/*
** main
**
** funzione principale che richiama tutte le altre
*/
int main(void) {
int m[MAX][MAX], n, v, pred;
struct nodo *lista[MAX];
n = leggi_grafo(&m[0][0]);
printf("Inserisci il vertice v: ");
scanf("%d", &v);
pred = verifica(&m[0][0], n, v);
if (pred >= 0) {
elimina_vertice(pred, v, &m[0][0], n);
nuovo_grafo(&m[0][0], &lista[0], n);
stampa_grafo(&lista[0], n);
} else {
printf("Il predecessore di %d non e` unico.\n");
}
return(0);
}