Занятие 4. Справочник

Занятие 4. Справочник

Алгоритм поиска в глубину компоненты связности графа, заданного матрицей смежности G 
static final int WHITE = 0;
static final int GREY  = 1;
static final int BLACK = 2;

static int[] color = new int [1000];

static void DFS(int v)
{
	color[v] = GREY;
	for (int i = 0; i < N; i++)
	{
		if (G[v][i] == 1 && color[i] == WHITE) DFS(i);
	}
	color[v] = BLACK;
}
Полный обход в глубину произвольного графа, заданного матрицей смежности G (например непосредственно в функции main) 
//по всем компонентам связности
for (int i = 0; i < N; i++)
{
	if (color[i] == WHITE)
	{  
		DFS(i);
	}
}
Проверка на двудольность 
//по всем компонентам связности
for (int i = 0; i < N; i++)
{
	if (color[i] == WHITE)
	{   part[i] = RED;
		DFS(i);
	}
}

if (!twoparted)
{
	out.println("NO");
}
else
{
	
	out.println("YES");
}
	
	static final int WHITE = 0;
	static final int GREY  = 1;
	static final int BLACK = 2;

	static int[] color = new int[1000];
	
	static final int RED  = 3;
static final int BLUE = 4;
static int[]  part = new int[1000];  
      //twoparted – если true – граф двудолен
      static boolean twoparted = true;

	static void DFS(int v)
	{
	    color[v] = GREY; 
	    
		for (int i = 0; i < N; i++)
		{  
			   if (G[v][i] == 1 && v != i) 
			   {
				   if (part[v] == part[i])
				   {
					   twoparted = false;
					   return;
				   }	   
				   if (color[i] == WHITE)
				   {	   
				       if (part[v] == RED) part[i] = BLUE;
				       else part[i] = RED;
					   DFS(i);
				   }	   
			   }
		}
		color[v] = BLACK;
	}

}