68
правок
Изменения
Новая страница: «Небольшая модификация алгоритма обхода в глубину позволяет проверить связность неориент…»
Небольшая модификация алгоритма обхода в глубину позволяет проверить связность неориентированного графа.
Один из вариантов алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.
string color[]; //изначально массив color заполнен значениями white.
int count = n; //счётчик количества вершин; изначально равен количеству вершин в графе
bool if_connected()
dfs(0); //запуск от какой-то вершины
if(count == 0)
return true;
else
return false;
int dfs(int u) //процедура обхода в глубину. запуск от номера вершины
for(v: uv - ребро)
if(color[v] == white)
dfs(v);
color[u] = black;
count--;
Один из вариантов алгоритма заключается в том, чтобы считать сколько вершин мы посетили во время обхода.
string color[]; //изначально массив color заполнен значениями white.
int count = n; //счётчик количества вершин; изначально равен количеству вершин в графе
bool if_connected()
dfs(0); //запуск от какой-то вершины
if(count == 0)
return true;
else
return false;
int dfs(int u) //процедура обхода в глубину. запуск от номера вершины
for(v: uv - ребро)
if(color[v] == white)
dfs(v);
color[u] = black;
count--;
