Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
darthw
0 / 0 / 0
Регистрация: 28.12.2009
Сообщений: 5
#1

Поиск ободов в графе - C++

28.12.2009, 07:35. Просмотров 655. Ответов 1
Метки нет (Все метки)

К сожалению не получается решить эту задачу на Си.
Вот исходный текст задачи:
"Найти в графе все подграфы, которые являются ободами".
К сведению обод это подграф имеющий 3 и более вершины причем vn входит в v0. Ну, в общем, ясно, что это цикл. Однако не получается найти их ВСЕ в графе..
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
28.12.2009, 07:35
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Поиск ободов в графе (C++):

Поиск циклов в графе. Поиск центра взвешенного графа - C++
В интернете, к сожалению, по этим вопросам не так уж много нашел. Можете посоветовать статью/пособие, где было бы подробно об этом написано?

Поиск на графе - C++
Доброго времени суток. Мне не совсем понятна реализация в коде поиска на графе в высоту и ширину. Т.к. в книге они описаны не совсем...

Поиск Ф-циклов в графе - C++
Нужно вывести на печать все фундаментальные циклы графа. Мой код выводит правильно(судя по данному примеру),но помоему он не разделяет сами...

Поиск мостов в графе - C++
Доброй ночи,задача состоит в отыскании мостов в графе. Много где есть в свободном доступе алгоритм примерно такого рода: ...

Поиск в ширину на графе - C++
#include "stdafx.h" #include "stdafx.h" #include <iostream> #include <conio.h> #include<vector> #include<queue> using namespace...

Поиск циклов в графе - C++
Как узнать что граф имеет цикл?

1
solar_wind
756 / 747 / 42
Регистрация: 06.07.2009
Сообщений: 2,970
Завершенные тесты: 1
28.12.2009, 08:49 #2
Ну можно решить задачу через деревья.
Число вершин графа ограничено, так что от каждой точки графа строишь дерево обхода его вершин, исключая повторения. После этого ищешь по дереву вершины, которые находятся ниже 2-го уровня и связаны с начальной вершиной, это и будут циклы. Можно начальную вершину включать в дерево, и использовать как один из критериев остановки просмотра, тогда останется только найти все вхождения начальной вершины в дереве.
Ну а потом удаляешь повторы и выводишь.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.12.2009, 08:49
Привет! Вот еще темы с ответами:

Поиск оптимального пути в графе - C++
Здравствуйте. Помогите, пожалуйста, написать код задачи по С++. необходимо найти минимальный путь в ориентированном графе, используя...

Поиск оптимальных путей в графе - C++
Нужно сделать библиотеку классов на тему Графов та поиска оптимальных путей. У меня есть задача, в которой реализован поиск опт.путей. Но...

Поиск кратчайшего пути в графе - C++
Задача: отыскать кратчайший путь между двумя заданными вершинами в произвольном ациклическом ориентированном графе с нагруженными ребрами. ...

Перебор/поиск с возвратом в графе - C++
Подскажите пожалуйста где я могу найти пример такой программы? Уже пару часов гуглю и нигде не найти. Хочу разобраться, а примеров программ...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru