Oppure

Loading
Questo topic e' stato chiuso dal moderatore.
25/05/13 8:29
aleandro03
ciao, ho fatto un programma che tramite bfs dovrebbe calcolare il cammino minimo di un grafo però quando mando in esecuzione il prgramma alla fine dell'esecuzione mi dice annullato core dump creato e praticamente non parte il programma e non capisco il motivo...per favore mi date una mano?adesso vi posto il codice


/*
 *  inclusione delle librerie
 */

#include <stdlib.h>
#include <stdio.h>


/*
 *  definizione della costante che indica la massima dimensione
 *  del grafo (|V|<MAX).
 */

#define MAX 100


/*
 *  definizione della struttura utilizzata per rappresentare i
 *  vertici del grafo nelle liste di adiacenza ed i nodi della
 *  coda Q.
 */

struct nodo {
  int info;
  struct nodo *next;
};


/*
 *  Legge in input una sequenza di n interi e li memorizza su
 *  una lista. Restituisce il puntatore al primo elemento della lista.
 */

struct nodo *leggi_lista(void) {
  struct nodo *p, *primo;
  int x, n, i, centrali;
  FILE *file_centrali;
  file_centrali = fopen("centrali.txt",
                        "r");
  fscanf(file_centrali,
         "%d",
         &centrali);
  printf("Numero centrali adiacenti: ");
  scanf("%d", &n);
  primo = NULL;
  for (i=0; i<n; i++) {
    scanf("%d", &x);
    p = malloc(sizeof(struct nodo));
    p->info = x;
    p->next = primo;
    primo = p;
  }
  return(primo);
}


/*
 *  Legge in input le n liste di adiacenza (una per ogni
 *  vertice del grafo G). Restituisce il numero di vertici
 *  di cui e' costituito il grafo e l'array di puntatori
 *  ai primi elementi di ogni lista di adiacenza.
 */

int leggi_grafo(struct nodo *lista[]) {
  int i, n, centrali;
  FILE *file_centrali;
  file_centrali = fopen("centrali.txt",
                        "r");
  fscanf(file_centrali,
         "%d",
         &centrali);
  printf("Numero totale di centrali: ");
  scanf("%d", &n);
  for (i=0; i<n; i++) {
    printf("Lista di adiacenza del vertice %d.\n", i);
    lista[i] = leggi_lista();
  }
  return(n);
}


/*
 *  accoda
 *
 *  aggiunge un nodo alla coda Q; "primo" punta la primo elemento,
 *  "ultimo" punta all'ultimo elemento della coda.
 */

void accoda(struct nodo **primo, struct nodo **ultimo, int x) {
  struct nodo *p;

  p = malloc(sizeof(struct nodo));
  p->info = x;
  p->next = NULL;
  if (*primo == NULL)
    *primo = p;
  if (*ultimo != NULL)
    (*ultimo)->next = p;
  *ultimo = p;
  return;
}


/*
 *  estrai
 *
 *  restituisce il primo elemento della coda e lo elimina dalla coda stessa.
 */

int estrai(struct nodo **primo, struct nodo **ultimo) {
  int r;

  if (*primo == NULL) {
    r = -1;
  } else {
    r = (*primo)->info;
    *primo = (*primo)->next;
  }
  return(r);
}


/*
 *  bfs
 *
 *  visita in ampiezza del grafo rappresentato tramite le liste di
 *  adiacenza l[0], ..., l[n-1]; la visita parte dal vertice s.
 */

void bfs(struct nodo *l[], int n, int d[], int pi[], int s) {
  struct nodo *primo, *ultimo, *v;
  int colore[MAX], i, u;

  primo = NULL;
  ultimo = NULL;
  for (i=0; i<n; i++) {
    colore[i] = 0;
    d[i] = -1;
    pi[i] = -1;
  }
  colore[s] = 1;
  d[s] = 0;
  accoda(&primo, &ultimo, s);
  while (primo != NULL) {
    u = estrai(&primo, &ultimo);
    v = l[u];
    while (v != NULL) {
      if (colore[v->info] == 0) {
        colore[v->info] = 1;
        d[v->info] = d[u] + 1;
        pi[v->info] = u;
        accoda(&primo, &ultimo, v->info);
      }
      v = v->next;
    }
    colore[u] = 2;
  }
  return;
}


/*
 *  Funzione principale.
 */

int main(void){
  int i, n, d[MAX], pi[MAX], sorgente;
  int centrali;
  FILE *file_centrali;
  file_centrali = fopen("centrali.txt",
                         "r");
  fscanf(file_centrali,
         "%d",
         &centrali);
  struct nodo *lista[MAX];

  n = leggi_grafo(lista);
  printf("Sorgente della visita: ");
  scanf("%d", &sorgente);
  bfs(lista, n, d, pi, sorgente);
  for (i=0; i<n; i++) {
    printf("Vertice %d: padre=%d, distanza=%d\n", i, pi[i], d[i]);
  fclose(file_centrali);
  }
  return(0);
}














aaa
25/05/13 15:08
pierotofy
Sembra che hai gia' ricevuto una risposta. forum.ubuntu-it.org/…
Il mio blog: piero.dev