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:
come posso fare per farla in modo ricorsiva?
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);
}
Ultima modifica da un moderatore: