Алгоритм поиска слова в заданном Графе

@AlexIach · Регистрация: 07.02.2015

Доброго времени суток. Может быть кто-то, когда-то писал такой алгоритм, для поиска слова в заданном графе. К примеру есть граф состоящий из 4 вершин пусть они имеют следующее значение S,U,N,P. Между вершинами стоят связи двусторонние, От S идёт к U,P
От U идёт к N,P
От N идёт к P
От P идёт к S
Подскажите как должен действовать алгоритм для того что бы проверить, можно ли с помощью этого графа составить введённое слово, к примеру SUN.

@Shamil1 · 04.08.2016, 15:40

Обход в ширину с поиском текущего пути в заранее подготовленном словаре.
Только нужно решить, что делать с циклами (можно или одну и ту же вершину-букву использовать несколько раз в одном слове)

@ProgJ · 04.08.2016, 23:46

А разве не достаточно проверить наличие рёбер SU и UN?
И если связи двусторонние, то почему, например, от N идет только в P? Должно идти и в U

@Shamil1 · 05.08.2016, 11:50

Сообщение от ProgJ

А разве не достаточно проверить наличие рёбер SU и UN?

Я когда отвечал, почему-то понял задачу как поиск любого (хоть какого-то слова) в графе.
Если искать конкретное слово, то надо найди все вершины с первой буквой и от каждой поиск в глубину.

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

@AlexIach 0 / 0 / 0 Регистрация: 07.02.2015 Сообщений: 68
		1
	Алгоритм поиска слова в заданном Графе 04.08.2016, 15:36. Показов 677. Ответов 3 Метки нет (Все метки) Доброго времени суток. Может быть кто-то, когда-то писал такой алгоритм, для поиска слова в заданном графе. К примеру есть граф состоящий из 4 вершин пусть они имеют следующее значение S,U,N,P. Между вершинами стоят связи двусторонние, От S идёт к U,P От U идёт к N,P От N идёт к P От P идёт к S Подскажите как должен действовать алгоритм для того что бы проверить, можно ли с помощью этого графа составить введённое слово, к примеру SUN. 0

@Shamil1 Модератор 2974 / 2121 / 451 Регистрация: 26.03.2015 Сообщений: 8,266
	04.08.2016, 15:40	2
	Обход в ширину с поиском текущего пути в заранее подготовленном словаре. Только нужно решить, что делать с циклами (можно или одну и ту же вершину-букву использовать несколько раз в одном слове) 0

@ProgJ 90 / 87 / 11 Регистрация: 20.11.2008 Сообщений: 724
	04.08.2016, 23:46	3
	А разве не достаточно проверить наличие рёбер SU и UN? И если связи двусторонние, то почему, например, от N идет только в P? Должно идти и в U 1

@Shamil1 Модератор 2974 / 2121 / 451 Регистрация: 26.03.2015 Сообщений: 8,266
	05.08.2016, 11:50	4
	Сообщение от ProgJ А разве не достаточно проверить наличие рёбер SU и UN? Я когда отвечал, почему-то понял задачу как поиск любого (хоть какого-то слова) в графе. Если искать конкретное слово, то надо найди все вершины с первой буквой и от каждой поиск в глубину. з.ы. Условия задачи нормально не сформулированы. Не ясно, - направленный граф или нет - можно ли одну вершину использовать несколько раз - могут ли разные вершины содержать одинаковые буквы 0

Опции темы