dfs求无向图生成树.txt

标准c++ acm算法实现,DFS求无向图生成树的算法.copy 至vc6.0 可编译

//dfs 求无向图生成树  from 算法导论
struct node
{
	int f , k, ft;
}l [ 100 ];

int n , g[ 100 ][ 100 ] , time;

int  main (  ) 
{
	int i ;
	memset ( l, 0 , sizeof ( l ) ;
	time = 0;
	for ( i = 1 ; i<= n ; i ++ )
		if ( l[ i ].ft == 0 )
			dfs (i ) ;
	
}


void dfs (int v )
{
	int u;
	time++;
	l[ v ].k = time;
	
	for ( u = 1 ; u<= n  ; u ++ )
	{
		if ( g [ u ] [v ] )
		{
			//标记G边
			if ( l[u].f==0 )
			{
				l[u].f = v;
				dfs ( v) ;	
			}
		}
	}
	time++;
	l[v].ft = time;
}