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,571 total views, 2 views today