[C] Visite in profondità e ampiezza di un grafo

[Downloader]

Avrei necessità di avere qualche esempio su come si effettuano in C le visite in profondità ed ampizza di un grafo.

Potreste darmi una mano?


Grazie

[Vincenzo1968]

La ricerca in profondità è simile all'attraversamento di un albero in preorder. La differenza sta nel fatto che nella prima bisogna tenere conto dei nodi già visitati.

Per la ricerca in ampiezza si utilizza una coda. Per visitare tutti i nodi connessi al nodo x, poniamo x nella coda ed entriamo in un loop in cui preleviamo il successivo nodo dalla coda e, se non è stato visitato, lo visitiamo inserendo successivamente nella coda tutti i nodi non visitati. Il processo continua finché la coda non è vuota.

l'esempio seguente usa una matrice di adiacenza:

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

#define MAX 5

struct node
{
	int data;
	struct node *link;
};

struct node *addqueue(struct node *p, int val)
{
	struct node *temp;
	if(p == NULL)
	{
		p = (struct node *) malloc(sizeof(struct node));
		if(p == NULL)
		{
			printf("Memoria insufficiente.\n");
			exit(0);
		}
		p->data = val;
		p->link=NULL;
	}
	else
	{
		temp = p;
		while(temp->link != NULL)
		{
			temp = temp->link;
		}
		temp->link = (struct node*)malloc(sizeof(struct node));
		temp = temp->link;
		if(temp == NULL)
        {
			printf("Memoria insufficiente.\n");
			exit(0);
		}
		temp->data = val;
		temp->link = NULL;
	}
	
	return(p);
}
struct node *deleteq(struct node *p,int *val)
{
	struct node *temp;
	if(p == NULL)
	{
		printf("La coda è vuota.\n");
		return(NULL);
	}

    *val = p->data;
    temp = p;
    p = p->link;

    free(temp);

    return(p);
}

void buildadjm(int adj[][MAX], int n)
{
	int i, j;
	for(i = 0; i < n; i++)
		for(j = 0; j < n; j++)
		{
		printf("Inserisci 1 se c'e' un arco fra %d e %d, altrimenti 0\n", i, j);
            scanf("%d", &adj[i][j]);
		}
}

void BreadthFirst(int adj[][MAX], int x, int visited[], int n, struct node **p)
{
	int y, j, k;

    *p = addqueue(*p, x);

	do
	{
		*p = deleteq(*p, &y);
		if(visited[y] == 0)
		{
			printf("\nNodo id = %d\t",y);
			visited[y] = 1;
			for(j = 0; j < n; j++)
				if((adj[y][j] == 1) && (visited[j] == 0))
					*p = addqueue(*p, j);
		}
	}while((*p) != NULL);
}

void DepthFirst(int x, int visited[], int adj[][MAX], int n)
{
   int j;
   visited[x] = 1;
   printf("Nodo id = %d\n", x);
   for(j = 0; j < n; j++)
      if(adj[x][j] == 1 && visited[j] == 0)
           DepthFirst(j, visited, adj, n);
}

void main()
{
	int adj[MAX][MAX], node, n;
	int i, visited[MAX];
	struct node *start = NULL;

	printf("Inserisci il numero dei nodi nel grafo. MAX = %d\n", MAX);
	scanf("%d", &n);

	buildadjm(adj, n);

	printf("\nVisita in DepthFirst\n");
	for(i = 0; i < n; i++)
		visited[i] = 0;
	for(i = 0; i < n; i++)
		if( !visited[i] )
			DepthFirst(i, visited, adj, n);

	printf("\nVisita in BreadthFirst\n");
	for(i = 0; i < n; i++)
		visited[i] = 0;
	for(i = 0; i < n; i++)
		if( !visited[i] )
			BreadthFirst(adj, i, visited, n, &start);
}