Является ли граф деревом [закрыт]
Закрыт. На этот вопрос невозможно дать объективный ответ. Ответы на него в данный момент не принимаются.
Хотите улучшить этот вопрос? Переформулируйте вопрос так, чтобы на него можно было дать ответ, основанный на фактах и цитатах.
Задачка: Предложите алгоритм, который определяет, является ли граф деревом. Мое решение, которое, как оказалась, неверное
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. Источник
Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является деревом, если граф — связный и в графе отсутствуют циклы. Проверку на связность я осуществляю с помощью поиска в глубину. Вопрос заключается в том, как мне «написать» проверку на циклы? В просмотренной литературе ничего подходящего найти не могу, либо написано сложно для понимая: векторы и т.д. Надеюсь на помощь начинающему программисту.
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, то мы идем в вершину, из которой еще не вышли, то есть образуем цикл.
Источник
Является ли граф деревом
Дан неориентированный невзвешенный граф. Необходимо определить, является ли он деревом.
Входные данные
В первой строке входного файла содержится одно натуральное число N (N ≤ 100) — количество вершин в графе. Далее в N строках по N чисел — матрица смежности графа: в i-ой строке на j-ом месте стоит 1, если вершины i и j соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
Выходные данные
Вывести «YES», если граф является деревом, и «NO» иначе.
Примеры
входные данные
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
выходные данные
NO
входные данные
3
0 1 0
1 0 1
0 1 0
выходные данные
YES
Мой код (реализован обход по графу в глубину + проверка на наличие петель):
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
n = int(input()) a = [] for i in range(n): a.append(list(map(int, input().split()))) vert = [0] color = [0]*n color[0] = 1 while len(vert) != 0: f = 0 for i in range(n): if a[vert[-1]][i] == 1 and color[i] == 0: vert.append(i) color[i] = 1 f = 1 break if f == 0: vert.pop() k = "YES" for i in color: if i == 0: k = 'NO' for i in range(n): if a[i][i] != 0: k = 'NO' print(k)
Источник
Дан неориентированный граф. Необходимо определить, является ли он деревом
Дан неориентированный граф. Необходимо определить, является ли он деревом.
Формат входных данных
В первой строке входного файла содержится одно натуральное число NN (1≤N≤1001≤N≤100) — количество вершин в графе. Далее в NN строках по NN чисел дана матрица смежности графа: в ii-ой строке на jj-ом месте стоит 1, если вершины ii и jj соединены ребром, и 0, если ребра между ними нет. На главной диагонали матрицы стоят нули. Матрица симметрична относительно главной диагонали.
Формат выходных данных
Требуется вывести «YES», если граф является деревом, и «NO» иначе.
Примеры
входные данные
6
0 1 1 0 0 0
1 0 1 0 0 0
1 1 0 0 0 0
0 0 0 0 1 0
0 0 0 1 0 0
0 0 0 0 0 0
выходные данные
NO
входные данные
3
0 1 0
1 0 1
0 1 0
выходные данные
YES
Вот прога, которая не проходит несколько тестов:
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
#include #include int components(int N, int *edges, int M) { int *rep = new int[N]; for (int i = 0; i N; ++i) rep[i] = i; for (int i = 0, p, q; i 2 * M; i += 2) { for (p = edges[i]; p != rep[p]; p = rep[p]); for (q = edges[i + 1]; q != rep[q]; q = rep[q]); if (p == q) continue; rep[p] = q; } int cnt = 0; return cnt; } int main() std::ifstream ifs("input.txt"); std::ofstream ofs("output.txt"); if (!ifs cnt = components(N, edges, M); std::cout :: endl; ofs :: endl; getchar(); getchar(); return 0; } Тесты, которые не проходят:
5
0 1 0 1 0
1 0 1 1 1
0 1 0 0 1
1 1 0 0 1
0 1 1 1 0
Вывод
NO
————————————————
10
0 0 1 1 0 0 1 0 0 1
0 0 1 1 0 0 1 1 1 1
1 1 0 0 1 1 1 0 1 1
1 1 0 0 1 0 0 1 1 0
0 0 1 1 0 1 1 1 1 0
0 0 1 0 1 0 1 1 1 1
1 1 1 0 1 1 0 0 1 1
0 1 0 1 1 1 0 0 1 1
0 1 1 1 1 1 1 1 0 0
1 1 1 0 0 1 1 1 0 0
Вывод
NO
Источник
Анализ алгоритма
Неориентированный граф, состоящий из 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» );
Источник