2016-11-14 1 views
1

им получать данные из базы данных с помощью PHP и конвертировать PHP-массив в JavaScript с помощью:движение через объект заполнен объектами

var dbarrayjs = <?php echo json_encode($dbarrayphp);?>;

Таким образом Js выходы один объект, где каждая запись в моей базе данных является сам объект. записи (одна строка моей базы данных) состоят из 2 строк. Одна из строк - это список номеров, разделенных символом «,», и их необходимо изменить на массив через string.split. Другая строка - простая цифра. Смысл этого заключается в описании предшественника древовидной системы. Строка с одиночной цифрой является узлом, а многозначная строка содержит все ее прямые родительские узлы. Одним из особых критериев является то, что все родители должны быть переданы для подтверждения ребенка.

Моя потребность - это способ пройти через эту систему и проверить, могу ли я достичь каждого элемента этого дерева или если есть один элемент, который не может быть достигнут из-за неправильного выбора предшественника. простой пример: Example predecessor tree

Редактировать: 21 марта 2017 г. - Я искал алгоритм верхнего уровня и не знал об этом тогда.

+0

Вы должны предоставить некоторые пробные данные и некоторый код, который вы пробовали до сих пор. Совет, напишите рекурсивную функцию, чтобы пройти через список, но имейте в виду игнорировать объект, если он уже был процессом, иначе вы получите бесконечный цикл. – Will

ответ

1

Это основной алгоритм теории графов. У вас есть ориентированный граф: соединения идут только в одном направлении. Если у вас есть заданный корневой узел, поиск довольно прост: выполните полный обход дерева корня (либо с глубиной, либо с breadth-first). Затем посмотрите, попали ли вы во все узлы.

Описание проблемы немного расплывчато: вам нужно только выяснить, отсутствует ли узел? Нужно ли это идентифицировать? Есть ли, возможно, только один недостающий узел? В зависимости от этих подробностей учет вашей реализации может потребовать немного больше работы.

Например, если все, что вам нужно сделать, это определить, отсутствует ли какой-либо узел, просто посчитайте узлы, когда вы их посещаете в своем поиске. Если конечный счетчик меньше количества узлов в базе данных, то у вас есть некоторые недостающие.

Если вы должны идентифицировать недостающие узлы, вы должны отслеживать, какие узлы вы посещали. Затем вам понадобится еще один блок кода, чтобы извлечь все узлы графика, сообщая те, которые не находятся в вашем «посещенном» списке.