Что нового

[Все] Полный путь в графе

Yashied

Модератор
Команда форума
Глобальный модератор
Есть следующий граф (дерево):


Из каждого узла может выходить максимум две ветки. Т.е. максимальное количество узлов (N) на каждом следующем уровне (i) удваивается по сравнению с предыдущим:

Код:
Ni = 2 ^ (i - 1)
Задается такой граф в виде последовательности строк, определяющих каждый уровень дерева, например:

Уровень 1: A
Уровень 2: B, C
Уровень 3: D, E, F, G
Уровень 4: H, I, J, K, L, M, N, O

и т.д.

A, B, C, ... - это просто названия узлов (могут быть произвольными).

Для полного описания графа используется массив:

$aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O']

Длина массива всегда равна максимально возможному количеству узлов в графе, в данном случае:

Код:
1 + 2 + 4 + 8 = 15
Если какие-нибудь узлы отсутствуют, то используются пустые строки, например:

Код:
$aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', '', 'H', '', '', 'I', 'J', 'K', '']



Самый верхний узел A (1-ый уровень) всегда должен присутствовать.

Задание

Написать алгоритм (функцию) для нахождения полного пути от вершины A до требуемого узла в таком дереве. Например, полный путь до узла J в предыдущем графе будет выглядеть так:


В качестве исходных данных есть только сам граф ($aGraph) и название узла в нем, например "J", путь до которого необходимо определить. Результат должен представлять из себя строку вида (для данного примера):

Код:
A-C-F-J
Примечание

Исходный граф может иметь произвольное количество уровней, начиная с 1, и произвольное количество отсутствующих вершин, но всегда имеет описанную выше древовидную структуру.
 

C2H5OH

AutoIT Гуру
Хотя, вообще-то рекурсию очень уважаю...

Код:
#include <Array.au3>

Dim $aGraph[15] = ['A', 'B', 'C', 'D', 'E', 'F', 'G', '', 'H', '', '', 'I', 'J', 'K', '']
$Uzel = "J"

$N = UBound($aGraph)
Dim $Derevo[$N]

For $i=1 to $N -1
	$Derevo[$i] = Floor( ($i-1) / 2 )
Next

$iIndex = _ArraySearch($aGraph, $Uzel)
If @error Then
    MsgBox(0, "Узел не найден", 'Узел "' & $Uzel & '" в дереве отсутствует.')
	Exit
EndIf

$sRes = ""

While $iIndex > 0
	$sRes = "-" & $aGraph[$iIndex] & $sRes
	$iIndex = $Derevo[$iIndex]
WEnd

$sRes = $aGraph[0] & $sRes

MsgBox(0, "Ответ", 'Путь : "' & $sRes & '"')
 

kaster

Мой Аватар, он лучший самый
Команда форума
Глобальный модератор
вот для этой задачи ассоциативные массивы не помешали бы. ну по крайней мере для того решения, которое я вижу
 
Автор
Yashied

Yashied

Модератор
Команда форума
Глобальный модератор
Ладно, раз больше никого нет, то вот мой вариант. Немного сложнее, но зато с рекурсией.

Код:
;~         A
;~       /   \
;~     B       C
;~   /   \       \
;~ D       E       F
;~       /       /   \
;~     G       H       I
;~           /   \
;~         J       K

Dim $aGraph[31] = ['A', 'B', 'C', 'D', 'E', '', 'F', '', '', 'G', '', '', '', 'H', 'I', '', '', '', '', '', '', '', '', '', '', '', '', 'J', 'K', '', '']

Func _Path(ByRef $aGraph, $sItem, $iIndex = 0, $sPath = '')
	If Not $aGraph[$iIndex] Then
		Return ''
	EndIf
	$sPath = StringRegExpReplace($sPath & '-' & $aGraph[$iIndex], '\A-+', '')
	If $aGraph[$iIndex] = $sItem Then
		Return $sPath
	EndIf
	$iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1
	If $iIndex < UBound($aGraph) - 1 Then
		For $i = 0 To 1
			Local $Path = _Path($aGraph, $sItem, $iIndex + $i, $sPath)
			If $Path Then
				Return $Path
			EndIf
		Next
	EndIf
	Return ''
EndFunc   ;==>_Path

ConsoleWrite(_Path($aGraph, 'K') & @CR)
 

C2H5OH

AutoIT Гуру
Не понимаю...
Код:
$iIndex = 2 ^ Ceiling(Log($iIndex + 2) / Log(2)) + 2 * ($iIndex - 2 ^ (Ceiling(Log($iIndex + 2) / Log(2)) - 1) + 1) - 1

:shok:

Почему не взять просто
Код:
$iIndex = 2 * $iIndex + 1

???
 
Верх