-1

I want to find the max path through a multidimensional array. It is set up like a tree structure.

EDIT: I guess what I am looking for is how to find a Maximum Spanning for an array.

$tree = [ 
    0 => '45', 
    1 => [ 
        0 => [ 
            0 => '3', 
            1 => [ 
                    0 => [0 => '88'],
                ], 
            ], 
        1 => [ 
            0 => '2', 
            1 => [ 
                    0 => [ 0 => '77'], 
                ], 
            ],
        2 => [ 
            0 => '5', 
            1 => [ 
                0 => [ 
                    0 => '67', 
                    1 => [ 
                        0 => [ 
                            0 => '2', 
                            1 => [ 
                                0 => [ 0 => '35' ], 
                                ], 
                            ], 
                        1 => [ 
                            0 => '3', 
                            1 => [ 
                                0 => [ 0 => '44' ], 
                                ], 
                            ], 
                        ], 
                    ], 
                ], 
            ], 
        ], 
    ];

What I want to do is feed this into a function and get back

1. Every unique set of paths like

45, 3, 88 = 136
45, 2, 77 = 124
45, 5, 67, 2, 35 = 154
45, 5, 67, 3, 44 = 164

2. Or the max path, just the highest of those.

164

I generate these trees from some pretty random data so they are sometimes 10s or hundreds of tiers and 100s or 1000s of unique paths.

Community
  • 1
  • 1
Bennington
  • 33
  • 5
  • What have you tried so far?????????? Create a TREE data structure and write a TREE traversal. – Dávid Szabó Sep 03 '14 at 17:21
  • What do you mean by max path? I'm mot sure where 164 comes from. –  Sep 03 '14 at 17:23
  • The 164 is the sum of 45, 5, 67, 3, 44 which turns out to be the largest unique path throught the tree. – Bennington Sep 03 '14 at 17:24
  • Possibly related: http://stackoverflow.com/q/4992664/697370 – Jeff Lambert Sep 03 '14 at 17:33
  • @watcher That is related. So I guess the real question is how would i write a Maximum spanning solution for this multidimensional array in PHP. – Bennington Sep 03 '14 at 19:06
  • I have tried referentially looping through the array and checking some parameters for each of the sub arrays (how many items and what type are they), but i haven't gotten that to work. Still working through that one. – Bennington Sep 03 '14 at 19:09
  • I think if you really want to do this, you're going to have to store that array in a different kind of data structure. Search around for adjacency matrix, I think you can store your weights in the 2-D array (rather than 1) and be able to perform a MST search on that. – Jeff Lambert Sep 03 '14 at 19:13

1 Answers1

-3

I believe you can perform this task more efficiently using array_walk_recursive.

Bruno Coelho
  • 1
  • I am not sure if that is true. I don't think I can access the parent objects within the array_walk_recursive. I have tried http://stackoverflow.com/questions/18447664/get-parent-array-name-after-array-walk-recursive-function and it didn't seem to get me where I wanted either. – Bennington Sep 03 '14 at 20:05