Анализ алгоритма
Неориентированный граф, состоящий из n вершин, будет деревом, если он связный и содержит n – 1 ребро. Запускаем поиск в глубину из первой вершины. Если существует обратное ребро, то граф имеет цикл и не является деревом. Одновременно в переменной с подсчитываем количество посещенных вершин в процессе поиска. Если по окончанию поиска в глубину оно не равно n, то граф не является связным.
Граф, приведенный в примере, является деревом.
Матрицу смежности графа храним в массиве m.
Функция dfs реализует поиск в глубину из вершины v. При этом в вершину v мы попали из вершины prev (prev = -1 если v – корень дерева поиска в глубину). В переменной с подсчитываем количество пройденных вершин в процессе поиска.
Ребро (v, i) будет обратным и образовывать цикл, если i ≠ prev и при этом вершина i уже была пройдена раньше (used[ i] = 1).
if (used[i]) flag = 1; else dfs(i,v);
Основная часть программы. Читаем входные данные.
Запускаем поиск в глубину из нулевой вершины. Поскольку она является корнем дерева поиска, то не имеет родителя. В качестве второго аргумента передаем функции dfs значение -1.
Граф не будет деревом, если существует обратное ребро (flag = 1) или граф не является связным (количество посещенных вершин c при поиске в глубину не равно n).
if (flag || (c != n)) printf( «NO\n» ); else printf( «YES\n» );
Если граф является деревом, то:
3. Граф не содержит циклов
Выполнение первых двух условий достаточно для того, чтобы граф являлся деревом.
Java реализация
public class Main
static int c = 0;
static int m [][], used [];
static void dfs( int v )
public static void main(String[] args ) //throws IOException
Scanner con = new Scanner(System. in );
//Scanner con = new Scanner(new FileReader («977.in»));
m = new int [ n ][ n ];
used = new int [ n ];
Arrays.fill( used , 0);
for ( int i = 0; i < n ; i ++)
for ( int j = 0; j < n ; j ++)
m [ i ][ j ] = con .nextInt();
if (( Edges == n — 1) && ( c == n ))
System. out .printf( «YES» );
System. out .printf( «NO» );
Источник
Определить, является ли неориентированный graph деревом (ациклический связный graph)
Учитывая неориентированный graph, проверьте, является ли он деревом или нет. Другими словами, проверьте, является ли данный неориентированный graph ациклическим связным graphом или нет.
Например, graph, показанный справа, является деревом, а graph слева не является деревом, так как содержит цикл 0—1—2—3—4—5—0 .
Рекомендуем прочитать:
Дерево — это неориентированный graph, в котором любые две вершины соединены ровно одним путем. Другими словами, любой ациклический связный graph является деревом. Мы можем легко определить ациклический связный graph, выполнив обход DFS на Graphе. Когда мы делаем поиск в глубину из любой вершины v в неориентированном Graph мы можем встретить обратное ребро, указывающее на одного из предков текущей вершины v в дереве ДФС. Каждое “заднее ребро” определяет цикл в неориентированном Graph. Если задний край x —> y , то так как y является предком узла x , у нас есть путь от y к x . Итак, можно сказать, что путь y ~~ x ~ y образует цикл. (Здесь, ~~ представляет еще одно ребро в пути, и ~ представляет прямое ребро) и не является деревом.
Алгоритм может быть реализован следующим образом на C++, Java и Python:
Источник
Является ли граф деревом [закрыт]
Закрыт. На этот вопрос невозможно дать объективный ответ. Ответы на него в данный момент не принимаются.
Хотите улучшить этот вопрос? Переформулируйте вопрос так, чтобы на него можно было дать ответ, основанный на фактах и цитатах.
Задачка: Предложите алгоритм, который определяет, является ли граф деревом. Мое решение, которое, как оказалась, неверное
bool is_rec( int arr[SIZE][SIZE], int current, int root, int find ) < bool endFlag = true; for(int i = 0; i < SIZE; ++i)< if((arr[current][i] == 1)&&(i!=root))< if(i!=find)< endFlag = endFlag&&is_rec(arr,i,current,find); >else < return false; >> > return endFlag; > bool IsTree( int arr[SIZE][SIZE] )
4 ответа 4
Дерево — связный граф с n-1 ребром.
bool dfs(int i, int arr[SIZE][SIZE], bool col[SIZE]) < if (col[i]) < return 0; >col[i] = true; for (int j = 0; j < SIZE; ++j) < if (ar[i][j]) < dfs(j, arr, col); >> > bool IsTree(int arr[SIZE][SIZE]) < int edges = 0; for (int i = 0; i < SIZE; ++i) < for (int j = i + 1; j < SIZE; ++j) < if (arr[i][j]) < edges++; >> > if (edges != SIZE - 1) < return false; >bool col[SIZE]; memset(col, 0, sizeof(col)); dfs(0, arr, col); for (int i = 0; i < SIZE; ++i) < if (!col[i]) < return false; >> return true; > Моё решение на Pascal. Граф задаётся матрицей смежности (1 — есть ребро, 0 — иначе). maxV — максимальное число вершин maxE — максимальное число рёбер Храню граф списком рёбер.
const maxV = 111; maxE = 111111*2; var n,m,i,j,x : longint; ef,es,next : array [1..maxE] of longint; first,last : array [1..maxV] of longint; c : longint; used : array [1..maxV] of boolean; flag : boolean; procedure add(v1,v2 : longint); begin inc(c); ef[c] := v1; es[c] := v2; if last[v1] <> 0 then next[last[v1]] := c; if first[v1] = 0 then first[v1] := c; last[v1] := c; end; procedure dfs(v,dad : longint); var h,e : longint; begin used[v] := true; h := first[v]; while h > 0 do begin e := es[h]; if used[e] and (e <> dad) then begin flag := false; exit; end; if e <> dad then dfs(e,v); if not flag then exit; h := next[h]; end; end; begin assign(input,'input.txt'); reset(input); assign(output,'output.txt'); rewrite(output); readln(n); for i := 1 to n do for j := 1 to n do begin read(x); if x = 1 then add(i,j); end; flag := true; dfs(1,1); for i := 1 to n do if not used[i] then flag := false; if not flag then writeln('NO') else writeln('YES'); end. Источник