Wed. Jun 12th, 2024

# Graphs – Tree Depth-first search

```In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path.
In other words, any acyclic connected graph is a tree. A forest is a disjoint union of trees.

// un graf daca este arbore afisati- i radacina
#include <fstream.h>

#include <mem.h>
#define DIM 100

typedef struct nod {
int vf;
nod* urm;
} *PNOD, NOD;

ofstream fout ("arbore.out");
ifstream fin ("arbore.in");

PNOD L[DIM]; //sir de pointeri la nod, care retin adresele listelor de vecini
int n, k; // nr de noduri
int v[DIM];  // v[i] = 1 nodul i a fost vizitat

void Citeste();
void Adauga(int i, int j); // ad la inceput
void DF(int nod);

int main()
{
Citeste();
int i;
for ( i = 1; i <= n; i++ ) // parcurg nodurile grafului
{
k = 0;
DF( i );
fout <<endl;
if ( k == n )
{
fout << " arbore cu rad " << i;
break;
}
memset( v, 0, sizeof( v ));
if ( i == n && k != n ) fout << " nu se poate " ;
}

fout.close();
fin.close();

return 0;
}

void Citeste()
{

int i, j;
fin >> n;
while ( fin >> i >> j )
{
Adauga(i, j);  // adauga pe i in lista lui j
}

}

void DF(int nod)
{
k++;
//	fout << nod << " ";
v[nod] = 1; // il vizitez
PNOD p = L[nod];    // pun in p adresa listei de vecini ai lui nod
while ( p )
{
if ( v[p->vf] == 0 ) DF(p->vf);    // de la primul vecin nemarcat, intru in recursie
p = p->urm;
}

}

void Adauga(int i, int j) // ad la inceput
{
PNOD p = new NOD;
p->vf = j;
p->urm = L[i];
L[i] = p;
}

```

35,354 total views, 1 views today