Взвешенные деревья

Тема в разделе "PHP", создана пользователем LEXAlForpostl, 1 июл 2012.

Модераторы: latteo
  1. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    740
    Симпатии:
    226
    Здравствуйте.
    Уважаемые коллеги, подскажите, пожалуйста, решение задачи.
    Необходимо создать взвешенное дерево(т.е. каждая связь будет есть свой вес=числовое значение).
    Необходимо иметь возможность добавлять наследника, указав номер родителя.

    UPD

    Появилась следующая идея реализации:
    Создаём два массива:
    1. Двумерный массив, первый индекс которого отвечает за уровень вложенности; второй индекс отвечает за те элементы, которые находятся на текущем уровне.
    2. Двумерный массив отношений. $relations[parent's_index][son's_index]=вес связи.

    Однако, как при такой структуре получить массив всех элементов, которые входят в поддерево родителя K? К может быть и корнем дерева, и листьями, и любым другим значением.
     
    Iwashka нравится это.
  2. -Dima-

    -Dima-

    Регистр.:
    3 окт 2009
    Сообщения:
    167
    Симпатии:
    66
    Не пойму, что вас смутило..
    ищите в первом массиве его индекс где он считается родителем, а со второго вытаскиваете его дерево..
    UPD Я наверно не внимательно прочитал... это в первом массиве у вас все связи, а во втором их вес...
    т.е. вам надо вытянуть все дерево родителя К из первого массива..
    Напишите ф-цию которая будет перебирать первый массив начиная с родителя К и проходить по всем его дочерним связям.
     
    Iwashka нравится это.
  3. LEXAlForpostl

    LEXAlForpostl

    Регистр.:
    21 май 2008
    Сообщения:
    740
    Симпатии:
    226
    Думал, может кто-то из коллег уже сталкивался с этим и функция у них уже имеется. Ибо работа с деревьями очень часто занятие. Поэтому и отписал на форуме.
     
    Iwashka нравится это.
  4. -Dima-

    -Dima-

    Регистр.:
    3 окт 2009
    Сообщения:
    167
    Симпатии:
    66
    я писал, у меня правда не так, но думаю идею поймете.

    допустим первый массив:
    PHP:
    $arr = array('p1'=> array('d1','d2','d3'),'d1' => array('a1','a2'));
    тогда ф-цию можно сделать такой:
    PHP:
    function searchchildren($father$array){
        if(
    $array[$father]){
            foreach(
    $array[$father] as $children){
                
    $child['children'][$children] = searchchildren($children$array);
            }
        }else{
            
    $child['children'] = null;
        }
        return 
    $child;
    }
     
    print_r(searchchildren('d1'$arr));
     
    Iwashka и LEXAlForpostl нравится это.