Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.55/11: Рейтинг темы: голосов - 11, средняя оценка - 4.55
Ёрик
47 / 47 / 3
Регистрация: 07.01.2009
Сообщений: 298
1

Поиск в ширину в графе

21.03.2010, 21:20. Просмотров 1931. Ответов 1
Метки нет (Все метки)

У меня есть небольшая база данных(обычный текстовый файл). Парсирую этот файл и полчается список списков,в котором первые элементы - вершины графа,а последующие - смежные вершины. Даже не знаю,ак выразиться,вроде бы, он взвешенный,но отношения задаются строкой. Я представляю, как можно было сделать,если значения были целочисленными или с плавающей запятой,тогда алгоритм Дейкстра реализовать,но граф получается особенный:
(картинка внизу)
Файл большой.

Пользователь должен ввести 2 вершины(строки),а результатом должен быть путь,например,введено "Александр" и "ВУЗ",тогда ложно быть выведено:

Александр является студентом
студент учится в ВШЭ
ВШЭ - это ВУЗ
Александр получил пятерку

Или введено "Александр" и "ВШЭ",тогда результат должен быть,наверное,таким:

Александр является студентом
студент учится в ВШЭ

p.s. граф представить в виде списка списков - условие задачи

Помогите с алгоритмом, я не представляю,как в этом случае ходить по графу от вершине к вершине, как быть с зацикливанием...
0
Миниатюры
Поиск в ширину в графе  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.03.2010, 21:20
Ответы с готовыми решениями:

Поиск в графе
Здравствуйте, есть следующая задача: Дан массив A длины (n+1), содержащий натуральные числа от 1...

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру...

Поиск циклов в графе
Подскажите, пожалуйста, какие идеи нужно применять к данной задаче

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых множество вершин...

Поиск критических элементов в графе
Критической вершиной в графе называется вершина, удаление которой приводит к разделению графа на 2...

1
ivpoed
1 / 1 / 2
Регистрация: 21.03.2010
Сообщений: 38
15.04.2010, 10:22 2
Не совсем вас понял, но есть подозрение, что в таком графе от вершины к вершине будет единственный путь - или не так? В таком случае - поиск в глубину + запоминание пути.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
15.04.2010, 10:22

Поиск кратчайшего пути в графе
Здравствуйте. Есть задача осуществить поиск кратчайшего пути между двумя заданными вершинами в...

Поиск нескольких кратчайших путей в графе
Добрый день всем! Такая казалось бы тривиальная задача для гуру программистов, но ничего толкового...

поиск цикла максимальной длинны в графе
Никто не подскажет как в неориентированном графе можно найти цикл максимальной длинны, включающий...


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

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

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