lista di archi collegati tra di loro in C

[mikael_c]

Come posso fare lista di archi collegati tra di loro in C per rappresentare un grafo?? avete qualche esempio??

[demos88]

Originariamente inviato da mikael_c

Come posso fare lista di archi collegati tra di loro in C per rappresentare un grafo?? avete qualche esempio??

Penso che più che creare una lista di archi, tu devi rappresentare un grafo nel suo complesso... potresti usare una matrice di adiacenza per esempio. In questo caso rappresenti gli archi in una matrice quadra di dimensione uguale al numero di nodi.

[mikael_c]

Va bene secondo voi cosi?? sembra che non parte


Il grafo G è rappresentato utilizzando la struttura dati delle liste di adiacenza, la sequenza S è rappresentata mediante una lista.


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

#define MAX 50

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

struct nodo *leggi_lista(void) {
struct nodo *p, *primo, *ultimo;
int a, i, n;

primo = NULL;
ultimo = NULL;
printf("Numero di elementi: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
scanf("%d", &a);
p = malloc(sizeof(struct nodo));
p->info = a;
p->next = NULL;
if (!primo)
primo = p;
if (ultimo)
ultimo->next = p;
ultimo = p;
}
return(primo);
}

int leggi_grafo(struct nodo *l[]) {
int i, n;

printf("Numero di vertici del grafo: ");
scanf("%d", &n);
for (i=0; i<n; i++) {
printf("Lista di adiacenza del vertice %d\n", i);
l[i] = leggi_lista();
}
return(n);
}

int adiacente(int u, int v, struct nodo *l[]) {
struct nodo *p;

p = l[u];
while (p!=NULL && p->info != v)
p = p->next;
if (p == NULL)
return(0);
else
return(1);
}

int hamiltoniano(struct nodo *primo, struct nodo *l[], int n) {
int visitato[MAX], i, flag;
struct nodo *p;

for (i=0; i<n; i++)
visitato[i] = 0;
p = primo;
visitato[p->info] = 1;
while (p->next != NULL && !visitato[p->next->info] && adiacente(p->info, p->next->info, l)) {
visitato[p->next->info] = 1;
p = p->next;
}
flag = 1;
for (i=0; i<n && flag==1; i++)
flag = visitato[i];
return(flag);
}

int main(void) {
struct nodo *lista[MAX], *primo;
int n;

n = leggi_grafo(lista);
primo = leggi_lista();
if (hamiltoniano(primo, lista, n))
printf("La sequenza di vertici e' un ciclo hamiltoniano in G.\n");
else
printf("La sequenza di vertici non e' un ciclo hamiltoniano.\n");
return(1);
}