Обход в глубину и компоненты связности
Основная идея поиска в глубину заключается в том, чтобы сначала взять непосещённую вершину в качестве начальной и, двигаясь по рёбрам текущей вершины, переходить к непосещённой вершине. Когда непосещённых вершин нет, вернуться к предыдущей вершине и продолжать пробовать другие вершины, пока все вершины не будут посещены.
Граф в приведённом ниже примере начинает обход с 0, а порядок показан на рисунке справа:

Максимальный связный подграф неориентированного графа G называется компонентой связности (или связной ветвью) графа G. Связный граф имеет только одну компоненту связности — самого себя; несвязный неориентированный граф имеет несколько компонент связности. Между компонентами связности нет рёбер. Поиск в глубину можно использовать для нахождения компонент связности.
Далее на примере поиска компонент связности реализуется обход графа в глубину, называемый dfs. В приведённом ниже фрагменте кода массив visited хранит, был ли узел посещён во время dfs, ccount хранит количество компонент связности, массив id представляет метку компоненты связности, соответствующую каждому узлу, а два узла с одинаковым значением id означают, что они принадлежат одной и той же компоненте связности.
// Конструктор, находит компоненты связности невзвешенного графа
public Components(Graph graph){
// Инициализация алгоритма
G = graph;
visited = new boolean[G.V()];
id = new int[G.V()];
ccount = 0;
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
id[i] = -1;
}
// Найти компоненты связности графа
for( int i = 0 ; i < G.V() ; i ++ )
if( !visited[i] ){
dfs(i);
ccount ++;
}
}
...
Обход графа в глубину — это рекурсивный процесс; код реализации:
// Обход графа в глубину
void dfs( int v ){
visited[v] = true;
id[v] = ccount;
for( int i: G.adj(v) ){
if( !visited[i] )
dfs(i);
}
}
...
Пример кода на Java
Загрузка пакета исходного кода:Скачать
код файла src/example/graph/Components.java:
import example.graph.read.Graph;
/**
* Обход в глубину
*/
public class Components {
Graph G; // Ссылка на граф
private boolean[] visited; // Отмечает, посещён ли узел во время обхода в глубину
private int ccount; // Записывает количество компонент связности
private int[] id; // Метка компоненты связности, соответствующая каждому узлу
// Обход графа в глубину
void dfs( int v ){
visited[v] = true;
id[v] = ccount;
for( int i: G.adj(v) ){
if( !visited[i] )
dfs(i);
}
}
// Конструктор, находит компоненты связности невзвешенного графа
public Components(Graph graph){
// Инициализация алгоритма
G = graph;
visited = new boolean[G.V()];
id = new int[G.V()];
ccount = 0;
for( int i = 0 ; i < G.V() ; i ++ ){
visited[i] = false;
id[i] = -1;
}
// Найти компоненты связности графа
for( int i = 0 ; i < G.V() ; i ++ )
if( !visited[i] ){
dfs(i);
ccount ++;
}
}
// Возвращает количество компонент связности графа
int count(){
return ccount;
}
// Проверяет, связаны ли узлы v и w
boolean isConnected( int v , int w ){
assert v >= 0 && v < G.V();
assert w >= 0 && w < G.V();
return id[v] == id[w];
}
}