Занятие 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;
}
}