Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является деревом, если граф — связный и в графе отсутствуют циклы. Проверку на связность я осуществляю с помощью поиска в глубину. Вопрос заключается в том, как мне «написать» проверку на циклы? В просмотренной литературе ничего подходящего найти не могу, либо написано сложно для понимая: векторы и т.д. Надеюсь на помощь начинающему программисту.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54
#include using namespace std; void dfs(int v, int **Array, int n, int *Array1) { Array1[v] = 1; for (int i = 0; i n; i++) { if (Array[v][i] == 1 && Array1[i] == 0) dfs(i, Array, n, Array1); } } int main() { //freopen("input.txt", "r", stdin); //freopen("output.txt", "w", stdout); int n; cin >> n; int **Array = new int *[n]; for (int i = 0; i n; i++) Array[i] = new int [n]; int *Array1 = new int [n]; for (int i = 0; i n; i++) { for (int j = 0; j n; j++) cin >> Array[i][j]; Array1[i] = 0; } dfs(n - 1, Array, n, Array1); for (int i = 0; i n; i++) { if (Array1[i] == 0) { cout <"NO" ; return 0; } } cout <"YES" ; return 0; } 
Является ли граф — деревом?
Доброго времени суток. Есть граф, нужно пробежаться по нему в ширину, и если не встретится циклов.
Определить, является ли граф деревом
Дан неориентированный граф, список инцидентности. Любым способом нужно определить, является ли он.
Дан неориентированный граф. Необходимо определить, является ли он деревом
Дан неориентированный граф. Необходимо определить, является ли он деревом. Формат входных данных.
Проверить, является ли ориентированный граф, с заданным количеством узлов и рёбер, деревом
Дан ориентированный граф из n узлов и m рёбер. Проверить, является ли он деревом. Помогите.
Сообщение было отмечено Catstail как решение
Решение
если у графа н-1 ребро и при этом он связен, то граф — дерево. Проверку на связность напишите сами?
Добавлено через 2 минуты
может быть не очевидно — если он связен и ребер ровно н-1, то циклов быть не может.
Добавлено через 19 минут
чуть позже прикреплю код проверки на циклы.
Добавлено через 6 часов 8 минут
int color[N]; void dfs(int v) { color[v] = 1; for(int i=0; i N; i++) if(g[v][i] != -1 && color[i] == 1) cycle_find = true; color[v] = 2; }
не умею я писать абстрактно. в общем, в чем дело: для каждой вершины мы храним так называемый «цвет». 0 — вершина не посещена до сих пор, 1 — дфс зашел в эту вершину, но еще не вышел, 2 — дфс вышел из вершины. таким образом, если мы идем в вершину с цветом 1, то мы идем в вершину, из которой еще не вышли, то есть образуем цикл.
Источник
Определить, является ли неориентированный 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. Источник