- Сообщения
- 5,379
- Репутация
- 2,724
Есть следующий граф (дерево):
Из каждого узла может выходить максимум две ветки. Т.е. максимальное количество узлов (N) на каждом следующем уровне (i) удваивается по сравнению с предыдущим:
Задается такой граф в виде последовательности строк, определяющих каждый уровень дерева, например:
Уровень 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']
Длина массива всегда равна максимально возможному количеству узлов в графе, в данном случае:
Если какие-нибудь узлы отсутствуют, то используются пустые строки, например:
Самый верхний узел A (1-ый уровень) всегда должен присутствовать.
Задание
Написать алгоритм (функцию) для нахождения полного пути от вершины A до требуемого узла в таком дереве. Например, полный путь до узла J в предыдущем графе будет выглядеть так:
В качестве исходных данных есть только сам граф ($aGraph) и название узла в нем, например "J", путь до которого необходимо определить. Результат должен представлять из себя строку вида (для данного примера):
Примечание
Исходный граф может иметь произвольное количество уровней, начиная с 1, и произвольное количество отсутствующих вершин, но всегда имеет описанную выше древовидную структуру.
Из каждого узла может выходить максимум две ветки. Т.е. максимальное количество узлов (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, и произвольное количество отсутствующих вершин, но всегда имеет описанную выше древовидную структуру.