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

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

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

Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней - C++

03.05.2011, 20:49. Просмотров 1044. Ответов 4
Метки нет (Все метки)

Помоги,будьте любезный.Всех прошу.Не могу написать сам алгоритм нахождения этого наибольшего пути.матрица смежности храниться в текстовом файле.буду очень рад если поможете.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2011, 20:49     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней
Посмотрите здесь:

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

Нахождение кратчайшего пути от одной вершины графа до другой - C++
Парни помогите доделать , в общем дан граф , я представил его связи в виде матрицы смежностей #include <iostream.h> #include...

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

нахождение Максимальной длины имени объекта Fat32 - C++
Прошу помощи,подсказки в решении такой вот задачки(С++Borland3.1) поиск объектов с максимальным количеством символов в имени среди...

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А - C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А. Никаких наработок нет, к сожалению, вообще...

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

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
03.05.2011, 22:56     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #2
Задача решается обходом в ширину, так как граф обязательно будет деревом.
God_Krom
1 / 1 / 0
Регистрация: 03.05.2011
Сообщений: 19
04.05.2011, 00:34  [ТС]     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #3
Если Тебе не тяжело,Ты бы не мог написать код этого обхода.
Veyron
106 / 106 / 4
Регистрация: 02.06.2009
Сообщений: 579
04.05.2011, 08:14     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #4
Обход в ширину

Это основной обход. Для решения задачи необходимо его расширить.
Массив посещений можно не сохрянять, потому что граф является ацикличным и мы не зациклимся на какой-то вершине, а иначе задача не решается (можно мотать бесконечно большой путь). Создадим массив расстояния от первой до текущей вершины. Сначала инициализируем все ячейки -1, а в первую пишем 0. Запускаем обход.
При обходе из всех выходящих из текущей вершин нужно прибавить по единице. При этом смотреть, нет ли там чего-то. Если есть, то сравнить значение, которое хотим присвоить и значение, которое уже есть там. Выбрать из них максимум и присвоить ячейке. В конце просто нужно вывести содержимое этого массива в последней ячейке.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.05.2011, 19:42     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней
Еще ссылки по теме:

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

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

В файле заменить все слова максимальной длины на слова минимальной длины - C++
Нужно в считанном из файла тексте заменить все слова максимальной длины на слова минимальной длины, а результат записать в новый файл....

Графы,исключение из пути определённых вершины - C++
Ребят!Есть программа:программа находит кратчайший путь в графе из точки а в точку б. Так вот как будет выглядеть функция которая будет...

Слово максимальной длины заменить на слово минимальной длины - C++
Задача: Создать 2 объекта разработанного класса. Одной из компонент класса является символьная строка. В результате выполнения программы...

Подсветить предложение максимальной длины - C++
С помощью текстового редактора Блокнот создать файл, содержащий текст, длина которого не превышает 1000 символов (длина строки не превышает...


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

Или воспользуйтесь поиском по форуму:
God_Krom
1 / 1 / 0
Регистрация: 03.05.2011
Сообщений: 19
04.05.2011, 19:42  [ТС]     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней #5
Спасибо большое.Буду пробовать.
Yandex
Объявления
04.05.2011, 19:42     Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней
Ответ Создать тему
Опции темы

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