Shane is given an edge array ($aEdges) and wants to

know the distinct connected components. This can be done

by my function connectedComponents($aEdges). The first

part walks each edge once to build an adjacency array.

The second part, which does the real work, picks an

unvisited edge and visits each vertex it can get to from

that selected vertex, processing each edge once, so that

the total running time is O(E). It'd be O(V+E) for the

second part, if singletons (isolated vertices) were

to have been allowed.

Csaba Gabor from Vienna

function connectedComponents ($aEdges) {

// given an edge array, $aEdges, this will return an array

// of connected components. Each element of the returned

// array, $aTrees, will correspond to one component and

// have an array of the vertices in that component.

$aAdj = array(); $aTree = array(); $ctr=-1;

foreach ($aEdges as $br) // Construct V/E adjacancy array

foreach ($br as $i=>$v) {

if (!array_key_exists($v,$aAdj)) $aAdj[$v]=array($br[1-$i]);

else array_push ($aAdj[$v], $br[1-$i]); }

foreach ($aAdj as $v =&$aTrees[++$ctr]) // Now build distinct

for ($i=0;$i<sizeof($aTrees[$ctr]);++$i) { // components

$aV = array_keys(array_flip(array_merge(

$aV = &$aTrees[$ctr], $aAdj[$aV[$i]])));

unset ($aAdj[$aV[$i]]); }

return $aTrees; }

//Example usage:

$aEdges = array(array (30, 31), array (29, 26),

array (29, 27), array (29, 28),

array (26, 27), array (27, 28));

$aComponents = connectedComponents ($aEdges);

//Example 2:

$aEdges = array(

array (a, b), array (b, d), array (b, e),

array (d, g), array (c, i), array (e, h),

array (h, j), array (c, f), array (f, i),

array (g, j), array (j, k), array(j, b));

$aComponents = connectedComponents ($aEdges);

On Dec 2, 6:33 pm, LittleCake <shaneda...@gmail.comwrote:

Hi All,

I have a multidimensional array where each sub-array contains just two

entries, which indicates a relationship between those two entries. for

example the first sub-array:

[0] =Array

(

[0] =30

[1] =31

)

This states that value 30 is related to 31. I would like to search

through the entire multidimensional array (it could be empty or

contain hundreds of entries), to see if multiple relationships exist

and hence group these relationships into one entry. so for the array

below:

Array

(

[0] =Array

(

[0] =30

[1] =31

)

[1] =Array

(

[0] =29

[1] =26

)

[2] =Array

(

[0] =29

[1] =27

)

[3] =Array

(

[0] =29

[1] =28

)

[4] =Array

(

[0] =26

[1] =27

)

[5] =Array

(

[0] =27

[1] =28

)

)

This should be represented as:

Array

(

[0] =Array

(

[0] =30

[1] =31

)

[1] =Array

(

[0] =29

[1] =26

[2] =27

[3] =28

)

)

I am new enough to PHP so I would appreciate your help.

Thanks