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