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

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

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

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

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

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

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

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

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

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

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

Поиск кратчайшего пути на графе - C++
Выдает ошибку Error 1 error C4996: 'itoa': The POSIX name for this item is deprecated. Instead, use the ISO C++ conformant name: _itoa. See...

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

Поиск кратчайших путей в графе - C++
Владислав Исенбаев — двукратный чемпион Урала по программированию, вице-чемпион TopCoder Open 2009, абсолютный чемпион ACM ICPC 2009. За то...

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

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

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

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


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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
solar_wind
756 / 747 / 42
Регистрация: 06.07.2009
Сообщений: 2,969
Завершенные тесты: 1
28.12.2009, 08:49     Поиск ободов в графе #2
Ну можно решить задачу через деревья.
Число вершин графа ограничено, так что от каждой точки графа строишь дерево обхода его вершин, исключая повторения. После этого ищешь по дереву вершины, которые находятся ниже 2-го уровня и связаны с начальной вершиной, это и будут циклы. Можно начальную вершину включать в дерево, и использовать как один из критериев остановки просмотра, тогда останется только найти все вхождения начальной вершины в дереве.
Ну а потом удаляешь повторы и выводишь.
Ответ Создать тему
Опции темы

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