Анализ алгоритма
Неориентированный граф, состоящий из 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:
Источник
Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является деревом, если граф — связный и в графе отсутствуют циклы. Проверку на связность я осуществляю с помощью поиска в глубину. Вопрос заключается в том, как мне «написать» проверку на циклы? В просмотренной литературе ничего подходящего найти не могу, либо написано сложно для понимая: векторы и т.д. Надеюсь на помощь начинающему программисту.
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, то мы идем в вершину, из которой еще не вышли, то есть образуем цикл.
Источник
Является ли граф — деревом?
Доброго времени суток. Есть граф, нужно пробежаться по нему в ширину, и если не встретится циклов, то это дерево.
Как сделать при обходе проверку на наличие циклов?
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 55 56 57 58
#include #include using namespace std; const int n=4; int i, j; //матрица смежности графа int GM[n][n] = { {0, 1, 1, 0}, {0, 0, 1, 1}, {1, 0, 0, 1}, {0, 1, 0, 0} }; //поиск в ширину void BFS(bool *visited, int unit) { int *queue=new int[n]; int count, head; for (i=0; in; i++) queue[i]=0; count=0; head=0; queue[count++]=unit; visited[unit]=true; while (headcount) { unit=queue[head++]; cout+ 1<" "; for (i=0; in; i++) if (GM[unit][i] && !visited[i]) { queue[count++]=i; visited[i]=true; } } delete []queue; } //главная функция int main() { setlocale(LC_ALL, "Rus"); int start; cout<"Стартовая вершина >> "; cin>>start; bool *visited=new bool[n]; cout<"Матрица смежности графа: "; for (i=0; in; i++) { visited[i]=false; for (j=0; jn; j++) cout<" "[ i][j]; cout; } cout<"Порядок обхода: "; BFS(visited, start-1); delete []visited; system("pause"); } Является ли граф деревом
Суть задачи заключается в том, что нужно проверить граф, является ли он деревом. Граф является.
Определить, является ли граф деревом
Дан неориентированный граф, список инцидентности. Любым способом нужно определить, является ли он.
Дан неориентированный граф. Необходимо определить, является ли он деревом
Дан неориентированный граф. Необходимо определить, является ли он деревом. Формат входных данных.
Проверить, является ли ориентированный граф, с заданным количеством узлов и рёбер, деревом
Дан ориентированный граф из n узлов и m рёбер. Проверить, является ли он деревом. Помогите.
1 2 3 4 5 6 7 8 9 10 11 12
if (GM[unit][i]) { if (!visited[i]) { queue[count++]=i; visited[i]=true; } else{ if (!GM[i][unit]) is_tree=false;//. } }
То есть, если мы посещали уже эту вершину, то мы зашли в цикл и это не дерево?
Добавлено через 15 минут
Сделал так
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82
#include #include using namespace std; const int n=4; int i, j; //матрица смежности графа int GM[n][n] = { {0, 1, 1, 0}, {1, 0, 0, 1}, {1, 0, 0, 0}, {0, 1, 0, 0} }; bool is_tree; //поиск в ширину void BFS(bool *visited, int unit) { int *queue=new int[n]; int count, head; for (i=0; in; i++) queue[i]=0; count=0; head=0; queue[count++]=unit; visited[unit]=true; while (headcount) { unit=queue[head++]; cout+ 1<" "; for (i=0; in; i++) { if (GM[unit][i] && !visited[i]) { queue[count++]=i; visited[i]=true; } if (GM[unit][i]) { if (!visited[i]) { queue[count++]=i; visited[i]=true; } else { if (!GM[i][unit]) is_tree=false;//. } } } } delete []queue; } //главная функция int main() { setlocale(LC_ALL, "Rus"); int start; cout<"Стартовая вершина >> "; cin>>start; bool *visited=new bool[n]; cout<"Матрица смежности графа: "; for (i=0; in; i++) { visited[i]=false; for (j=0; jn; j++) cout<" "[ i][j]; cout; } cout<"Порядок обхода: "; BFS(visited, start-1); cout ; cout <"Что получилось: " ; delete []visited; system("pause"); } Не знаю правильно ли понял, но какое бы дерево я не подставлял, все равно говорит что «0» — не дерево
Сообщение от Shadow0671 
Не знаю правильно ли понял, но какое бы дерево я не подставлял, все равно говорит что «0» — не дерево
потому что программист из тебя плохой. Ты не профессионал. Всё-таки алгоритмы на графах предполагают, что автор хотя бы полгода потратил на самостоятельное программирование всяких простых алгоритмов, которые бы научили его понятию «логический флаг», «переменные надо инициализировать», «а почему именно при этом условии в if. » «А что именно именяет проверка if(GM[unit][i])»и.т.д.
Зла не хватает, блин, признавайся, ты не сам писал эту программу! И вообще ты не программист! Я когда отвечал, думал, что разговариваю с создателем программы.
Это костыль. Примеров поиска в ширину много в сети. Я попросил помощи (вы то и помогли), спасибо вам за это. Но зачем разводить такой кипишь. Не легче показать как это делается? Будет полезно мне и всем последующим кто обратиться на форум с таким же вопросом.
Сообщение было отмечено Shadow0671 как решение
Решение
Перерд тем как копировать что-то куда-то нужно осознавать, зачем ты копируешь:
Вглядись внимательно в этот код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
if (GM[unit][i] && !visited[i]) { queue[count++]=i; visited[i]=true; } if (GM[unit][i]) { if (!visited[i]) { queue[count++]=i; visited[i]=true; } else { if (!GM[i][unit]) is_tree=false;//. } }
Если бы ты сам написал первую строчку, у тебя бы сразу возникла мысль «а чего это вдруг в седьмой строке то же самое повторяется»? Но нет, для тебя хоть первая строчка, хоть последняя — всё китайская грамота!
А ведь посмотреть на эту строчку стоило. Потому что мой код делает точно то же самое, а значит не дополняет этот блок if, а полностью заменяет его! Заменяет значит следует сделать так
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
for (i=0; in; i++) { if (GM[unit][i]) { if (!visited[i]) { queue[count++]=i; visited[i]=true; } else { if (!GM[i][unit]) is_tree=false;//. } } }
Пробуй это, и я надеюсь, ты добавишь в нужное место кода строку is_tree=true
Добавлено через 15 минут
Вот полный код и извини за то, что ёрничаю и чешу тем самым своё ЧСВ. Но блина. чтобы даже просто скопипастить что-то в скопипащеный же ранее код, в нём же разбираться тоже надо!
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 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73
#include #include using namespace std; const int n = 4; int i, j; //матрица смежности графа int GM[n][n] = { { 0, 1, 1, 0 }, { 1, 0, 0, 1 }, { 1, 0, 0, 0 }, { 0, 1, 0, 0 } }; bool is_tree; //поиск в ширину void BFS() { int *queue = new int[n]; bool *visited = new bool[n]; int count, head; for (i = 0; in; i++) queue[i] = 0; count = 0; head = 0; queue[count++] = 0; visited[0] = true; is_tree = true; while (headcount) { int unit = queue[head++]; cout + 1 <" "; for (i = 0; in; i++) { if (GM[unit][i]) { if (!visited[i]) { queue[count++] = i; visited[i] = true; } else { if (!GM[i][unit]) is_tree = false;//. } } } } delete[]queue; delete[]visited; } //главная функция int main() { setlocale(LC_ALL, "Rus"); cout <"Матрица смежности графа: " ; for (i = 0; in; i++) { for (j = 0; jn; j++) cout <" " [ i][j]; cout ; } cout <"Порядок обхода: "; BFS(); cout ; cout <"Что получилось: " <(is_tree?"дерево":"не дерево") ; system("pause"); } Источник