grafi orientati

Stato
Discussione chiusa ad ulteriori risposte.

sare1234

Utente Attivo
262
3
Buon pomeriggio devo realizzare un programma in c che dato un grafo mi permette di calcolare i gradi uscenti e entranti di ogni vertice con matrice di adiacenza e con lista di adiacenza: ho fatto quella con lista di adiacenza in modo iterativo:
C:
/* 1. leggi e stampa un grafo orientato mediante liste di adiancenza;


   2. calcola e stampa il grado entrante ed uscente di ciascun nodo*/


#include <stdio.h>
#include <stdlib.h>
#define MAX 100

struct nodo {
int info;
struct nodo *next;

};

/* legge una lista di n interi memorizzandola in una pila */
struct nodo *leggi_pila(void) {
int  x;
struct nodo *primo=NULL, *p;
scanf("%d", &x);
while(x != -1) {
  p = malloc(sizeof (struct nodo));
  p->info = x;
  p->next = primo;
  primo = p;
  scanf("%d", &x);
}
return(primo);
}


/* con notazione matriciale */
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("inserci il numero di nodi: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
  printf("inserisci i nodi adiacenti al nodo %d (interrompi con -1): ", i);
  G[i] = leggi_pila();
}
return(n);
}


void stampa_lista(struct nodo *primo) {
struct nodo *p=primo;
while(p!=NULL){
  printf("%d --> ", p->info);
  p=p->next;
}
printf("NULL.\n");
return;
}

/* stampa grafo come liste di adiacenza */
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("stampo il grafo come liste di adiacenza: \n");
for (i=0; i<n; i++) {
  printf("stampa la lista dei nodi adiacenti ad %d: ", i);
  stampa_lista(G[i]);
}
return;
}

/* calcola grado (entrante ed uscente) di ciascun nodo */
void grado(struct nodo *G[], int W[MAX][2], int n) {
int i, j;
/* inzialiazzo la matrice con tutti gli elementi a zero */
for (i=0; i<n; i++) {
  for (j=0; j<2; j++) {
      W[i][j]=0;
  }
}


  



struct nodo *p;
for (i=0; i<n; i++) {
  p = G[i];
  while (p != NULL) {
  W[i][1]++;        /* incremento di 1 il numero di nodi uscenti "OUT" */
  W[p->info][0]++;  /* incremento di 1 il numero di nodi entranti "IN" */
   p = p->next;
  }
}

return;

}



/* stampa matrice di interi */
void stampa_grado(int W[MAX][2], int n){
int i, j;
for (i=0;i<n;i++) {
  printf("stampo grado IN e OUT nodo %d: ", i);
  for (j=0; j<2; j++) {
   printf("%d ", W[i][j]);

  }
  printf("\n");
}
return;
}


/* funzione principale */
int main (void) {
struct nodo *G[MAX];
int n;
n = leggi_grafo(G);
stampa_grafo(G, n);

int W[n][2]; /* W[i][0] indica il numero di nodi entranti (IN) al nodo
  W[i][1] indica il numero di nodi uscenti (OUT) al nodo i   */
grado(G,W,n);
stampa_grado(W,n);
return(0);
}
come posso fare per farla in modo ricorsiva?
 
Ultima modifica da un moderatore:

ilfe98

Moderatore
Staff Forum
Utente Èlite
3,049
1,277
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
Buon pomeriggio devo realizzare un programma in c che dato un grafo mi permette di calcolare i gradi uscenti e entranti di ogni vertice con matrice di adiacenza e con lista di adiacenza: ho fatto quella con lista di adiacenza in modo iterativo:
C:
/* 1. leggi e stampa un grafo orientato mediante liste di adiancenza;


   2. calcola e stampa il grado entrante ed uscente di ciascun nodo*/


#include <stdio.h>
#include <stdlib.h>
#define MAX 100

struct nodo {
int info;
struct nodo *next;

};

/* legge una lista di n interi memorizzandola in una pila */
struct nodo *leggi_pila(void) {
int  x;
struct nodo *primo=NULL, *p;
scanf("%d", &x);
while(x != -1) {
  p = malloc(sizeof (struct nodo));
  p->info = x;
  p->next = primo;
  primo = p;
  scanf("%d", &x);
}
return(primo);
}


/* con notazione matriciale */
int leggi_grafo(struct nodo *G[]) {
int i, n;
printf("inserci il numero di nodi: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
  printf("inserisci i nodi adiacenti al nodo %d (interrompi con -1): ", i);
  G[i] = leggi_pila();
}
return(n);
}


void stampa_lista(struct nodo *primo) {
struct nodo *p=primo;
while(p!=NULL){
  printf("%d --> ", p->info);
  p=p->next;
}
printf("NULL.\n");
return;
}

/* stampa grafo come liste di adiacenza */
void stampa_grafo(struct nodo *G[], int n) {
int i;
printf("stampo il grafo come liste di adiacenza: \n");
for (i=0; i<n; i++) {
  printf("stampa la lista dei nodi adiacenti ad %d: ", i);
  stampa_lista(G[i]);
}
return;
}

/* calcola grado (entrante ed uscente) di ciascun nodo */
void grado(struct nodo *G[], int W[MAX][2], int n) {
int i, j;
/* inzialiazzo la matrice con tutti gli elementi a zero */
for (i=0; i<n; i++) {
  for (j=0; j<2; j++) {
      W[i][j]=0;
  }
}


 



struct nodo *p;
for (i=0; i<n; i++) {
  p = G[i];
  while (p != NULL) {
  W[i][1]++;        /* incremento di 1 il numero di nodi uscenti "OUT" */
  W[p->info][0]++;  /* incremento di 1 il numero di nodi entranti "IN" */
   p = p->next;
  }
}

return;

}



/* stampa matrice di interi */
void stampa_grado(int W[MAX][2], int n){
int i, j;
for (i=0;i<n;i++) {
  printf("stampo grado IN e OUT nodo %d: ", i);
  for (j=0; j<2; j++) {
   printf("%d ", W[i][j]);

  }
  printf("\n");
}
return;
}


/* funzione principale */
int main (void) {
struct nodo *G[MAX];
int n;
n = leggi_grafo(G);
stampa_grafo(G, n);

int W[n][2]; /* W[i][0] indica il numero di nodi entranti (IN) al nodo
  W[i][1] indica il numero di nodi uscenti (OUT) al nodo i   */
grado(G,W,n);
stampa_grado(W,n);
return(0);
}
come posso fare per farla in modo ricorsiva?
Ciao, premetto di non aver capito bene l'esercizio dato che l'ho letto con molta velocità. La prima domanda è, non potresti utilizzare una calloc anziche la malloc, nel primo utilizzo è identico alla malloc, successivamente quando nell'heap è gia presente un valore la calloc si comporta da realloc aumentando lo spazio, vantaggi? Inizializza già a 0 le celle. Comunque sia l'esercizio da te richiesto. Lo scorrimento della lista mediante ricorsione è univoco. La ricorsione si basa sulla chiamata alla stessa funzione più volte. Perciò avrai bisogno di un indice iniziale per considerare la profondità a cui ti trovi ed un valore di abort() nel tuo caso -1 se non erro. Nel momento in cui tu chiamerai la funzione mediante ricorsione dovrai ricordare di aggiornare il tuo puntatore all'indirizzo successivo.
N.B. Mediante ricorsione perderai l'indirizzo iniziale, come puoi ovviare a ciò?
P.s. Io preferisco il ragionamento costruttivo. Non ti risolverò l'esercizio, ma proverò a farti capire ciò che non è chiaro. Spero che questo modus operandi venga apprezzato
 

sare1234

Utente Attivo
262
3
Ciao, premetto di non aver capito bene l'esercizio dato che l'ho letto con molta velocità. La prima domanda è, non potresti utilizzare una calloc anziche la malloc, nel primo utilizzo è identico alla malloc, successivamente quando nell'heap è gia presente un valore la calloc si comporta da realloc aumentando lo spazio, vantaggi? Inizializza già a 0 le celle. Comunque sia l'esercizio da te richiesto. Lo scorrimento della lista mediante ricorsione è univoco. La ricorsione si basa sulla chiamata alla stessa funzione più volte. Perciò avrai bisogno di un indice iniziale per considerare la profondità a cui ti trovi ed un valore di abort() nel tuo caso -1 se non erro. Nel momento in cui tu chiamerai la funzione mediante ricorsione dovrai ricordare di aggiornare il tuo puntatore all'indirizzo successivo.
N.B. Mediante ricorsione perderai l'indirizzo iniziale, come puoi ovviare a ciò?
P.s. Io preferisco il ragionamento costruttivo. Non ti risolverò l'esercizio, ma proverò a farti capire ciò che non è chiaro. Spero che questo modus operandi venga apprezzato
l'esercizio è dato un grafo calcola il grado uscente ed entrante
Post unito automaticamente:

l'esercizio è dato un grafo calcola il grado uscente ed entrante con lista di adiacenza e matrice di adiacenza
 

ilfe98

Moderatore
Staff Forum
Utente Èlite
3,049
1,277
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
l'esercizio è dato un grafo calcola il grado uscente ed entrante
Post unito automaticamente:
Ok si lo avevo letto. Intendevo dire che è stato letto velocemente con qualcosa che sfuggiva. Il tema principale l'ho compreso. Comunque ti ho scritto un paio di cose le hai lette?
 

sare1234

Utente Attivo
262
3
Ok si lo avevo letto. Intendevo dire che è stato letto velocemente con qualcosa che sfuggiva. Il tema principale l'ho compreso. Comunque ti ho scritto un paio di cose le hai lette?
si m con ricorsione non riesco a capire come realizzarlo cioè ho due strutture una che rappresenta il grafo e l'atra che rappresenta la lista di adiacenza poi ho bisogno della funzione per inizializzare il grafo, per inizializzare la lista, per stampare grafo e lista e poi una che calcola il grado uscente e entrante giusto?
 

ilfe98

Moderatore
Staff Forum
Utente Èlite
3,049
1,277
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
Esatto, La ricorsione su lista è molto semplice
Esempio su stampa
C:
struct nodo {
int info;
struct nodo *next;

};
// Potresti usare anche il typedef per definire la struct come lista, nodo o quello che vuoi
typedef struct nodo lista;
void stampa_lista(lista *p){
if (p->next==NULL)
abort();
else
printf("%d",p->info);
stampa_lista(p->next);
}
Questo è un esempio di stampa con ricorsione. N.B in questo modo non perdi l'indirizzo del primo elemento. Con questa metodologia riesci a scorrere l'intera lista finchè il prossimo è diverso dal nullo. Cosa intendi per inizializzare? Per leggere una lista e memorizzarla in una pila usi questo metodo con la realloc e non la malloc
 

sare1234

Utente Attivo
262
3
Esatto, La ricorsione su lista è molto semplice
Esempio su stampa
C:
struct nodo {
int info;
struct nodo *next;

};
// Potresti usare anche il typedef per definire la struct come lista, nodo o quello che vuoi
typedef struct nodo lista;
void stampa_lista(lista *p){
if (p->next==NULL)
abort();
else
printf("%d",p->info);
stampa_lista(p->next);
}
Questo è un esempio di stampa con ricorsione. N.B in questo modo non perdi l'indirizzo del primo elemento. Con questa metodologia riesci a scorrere l'intera lista finchè il prossimo è diverso dal nullo. Cosa intendi per inizializzare? Per leggere una lista e memorizzarla in una pila usi questo metodo con la realloc e non la malloc
va bene in realtà volevo farlo senza l'uso della pila ed ho fatto cosi

devo realizzare una funzione che calcola il massimo grado uscente ed entrante...puoi aiutarmi? :)
 
Ultima modifica:

ilfe98

Moderatore
Staff Forum
Utente Èlite
3,049
1,277
CPU
Intel i7 7700K
Dissipatore
Bequiet Dark rock pro 4
Scheda Madre
Msi pc mate z270
HDD
Seagate barracuda 1tb, silicon power NVME 500gb
RAM
Patriot viper steel 3733Mhz
GPU
Inno 3d gtx 1080 herculez design
Monitor
Asus mg279q
PSU
Corsair HX750
Case
Itek lunar 23
Net
Tiscali ftth
OS
windows 10,mint,debian,Arch linux
va bene in realtà volevo farlo senza l'uso della pila ed ho fatto cosi

devo realizzare una funzione che calcola il massimo grado uscente ed entrante...puoi aiutarmi? :)
Forse non mi sono spiegato bene. Non fornisco le soluzioni! Devi realizzare la funzione? Ben venga,ma deve essere una soluzione ragionata. Che problemi riscontri ?
 
Stato
Discussione chiusa ad ulteriori risposte.

Ci sono discussioni simili a riguardo, dai un'occhiata!

Entra

oppure Accedi utilizzando
Discord Ufficiale Entra ora!

Discussioni Simili