|
|
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
Есть некий хэш, содержащий в качестве ключа названиеА, а в качестве значения названиеБ. Как обойти и составить полный список "пути" для каждого узла где названиеБ предыдущего шага = названиеА текущего. Включая пути, которые закольцовываются - заканчиваются там где и начинаются. Код: php 1. 2. 3. 4. 5. 6. 7. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.05.2013, 09:21 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
Для этого применяется рекурсия ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.05.2013, 10:43 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
skole, понятно что рекурсия, но на каком то месте завис и все, мыслей нет. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.05.2013, 12:29 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
Кидаешь все узлы и линки в массив и начинаешь обход в два приема, у тебя плоский граф, проблем не должно быть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.05.2013, 12:53 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
skole, Не должно, но есть. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.05.2013, 13:12 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
Собери все узлы в одну коллекцию, а линки в другую, начинай обход в цикле, построй логику цикла таким образом, чтобы получить результат. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.05.2013, 13:34 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
skoleКидаешь все узлы и линки в массив и начинаешь обход в два приема, у тебя плоский граф, проблем не должно быть. Почему массив. Эта структура неудачна для поиска уже существующих на предмет циклов. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 22.05.2013, 15:06 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
philipp1, Храни найденные пути в виде массива хешей, и при добавлении нового участка просто проверяй, есть он уже в этом хеше или нет. Как только встретился - все, стоп, началось зацикливание. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.05.2013, 09:40 |
|
||
|
Полный обход графа
|
|||
|---|---|---|---|
|
#18+
skoleКидаешь все узлы и линки в массив и начинаешь обход в два приема, у тебя плоский граф, проблем не должно быть. +1 вот тут именно по такому принципу и решалась подобная задача. Разница лишь в том, что там новый элемент добавлялся только к одному родителю (прошлому элементу), а в данном случае надо добавлять к двум как я понял (так как у рёбер графа нету направленности). При данном методе зацикленности не будет, так как пройдя все элементы по очереди произойдёт выход из цикла и всё :) P.S. код на js ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 23.05.2013, 13:18 |
|
||
|
|
start [/forum/topic.php?fid=16&msg=38268149&tid=1341802]: |
0ms |
get settings: |
10ms |
get forum list: |
11ms |
check forum access: |
2ms |
check topic access: |
2ms |
track hit: |
339ms |
get topic data: |
14ms |
get forum data: |
3ms |
get page messages: |
65ms |
get tp. blocked users: |
2ms |
| others: | 246ms |
| total: | 694ms |
| 0 / 0 |
