Graphs – related components(algorithm)

  To determine connected components we use the method of access
  depth of a graph. Algorithm steps are:
-P1: Is seeking a knot yet unvisited
-P2: It takes up to all nodes accessible and unvisited
taking care to mark the visit acestora.Toate these nodes
form a connected component
-P3: Unvisited nodes if there is going to step P1, otherwise STOP

/* Pentru detrminarea componentelor conexe vom utiliza metoda de vizitare
in adancime a unui graf. Pasii algoritmului sunt urmatorii:
-P1: se cauta un nod inca nevizitat
-P2: se parcurg de la acesta toate nodurile accesibile si nevizitate
	 avand grija sa marcam vizitarea acestora.Toate aceste noduri
	 formeaza o componenta conexa
-P3: daca mai exista noduri nevizitate mergi la pasul P1,altfel STOP*/
#include <stdio.h>
#include <memory.h>


#define MAX 100
#define TRUE 1
#define FALSE 0

//nr de noduri din graf
int n;

//modul de la care se porneste vizitarea
int nodi;

//matricea de adiacenta
char vecin[MAX][MAX];

//vector care pastreaza starea unui nod vizitat sau nevizitat
char vizitat[MAX];


//se citesc nr de noduri si matricea de adiacenta
void cit_date()
{
	int i,j;

	printf("Nr.Varfuri = ");
	scanf("%d",&n);
	for (i=0;i<n-1;i++)
	 for (j=i+1;j<n;j++)
	 {
		printf("a[%d,%d]= ",i,j);
		scanf("%d",&vecin[i][j]);
		vecin[j][i] = vecin[i][j];
	 }
	 printf("Nodul initial = ");
	 scanf("%d",&nodi);
	 memset(vizitat,0,sizeof(vizitat));
}

void dfs(int k)
{
	int i;

	vizitat[k] = 1;
	printf("(%d) ",k);

	for (i=0;i<n;i++)
		if(vizitat[i] == 0 && vecin[k][i] == 1)
			dfs(i);
}

void main()
{
	int i,x;

	cit_date();
	x = 0;

	for (i=0;i<n;i++)
		if(vizitat[i] == FALSE)
		{
			x++;
			printf("Componenta conexa %d : ",x);
			dfs(i);
			printf("\n");
		}
}

394,591 total views, 1 views today