Share

# 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;

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");
}
}```

72,091 total views, 469 views today