Как определить в массиве элементы, которые взаимосвязаны или влияют друг на друга?

Question

Эльзара

рекурсия , php , массивы

Как определить в массиве элементы, которые взаимосвязаны или влияют друг на друга?

Как можно получить зацикленные цепочки значений в данном массиве, где каждое значение связано с другим, например:

<pre><code class="php">Array
(
    [385] =&gt; 392
    [386] =&gt; 392
    [387] =&gt; 392
    [390] =&gt; 402
    [402] =&gt; 421
    [405] =&gt; 401
    [409] =&gt; 416
    [410] =&gt; 401
    [414] =&gt; 402
    [416] =&gt; 389
    [420] =&gt; 421
    [421] =&gt; 422
    [422] =&gt; 420
)</code></pre> 

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

10 ноября 2024 г. 3:03

Ответы на вопрос 2

Похожие вопросы

Answer 1

Для выявления зацикленных цепочек в массиве, где элементы взаимосвязаны, можно использовать метод поиска в глубину (DFS, depth-first search). В PHP это можно реализовать с помощью рекурсивной функции. Мы будем отслеживать посещенные узлы и узлы, находящиеся на текущем пути, чтобы определить циклы.

Вот пример кода, который реализует данное решение:

```php
function findCycles($array) {
    $visited = [];
    $recStack = [];
    $cycles = [];
    
    foreach ($array as $node => $value) {
        if (!isset($visited[$node])) {
            $stack = [];
            dfs($node, $array, $visited, $recStack, $stack, $cycles);
        }
    }
    
    return $cycles;
}

function dfs($node, $array, &$visited, &$recStack, &$stack, &$cycles) {
    $visited[$node] = true;
    $recStack[$node] = true;
    $stack[] = $node;

    if (isset($array[$node])) {
        $neighbour = $array[$node];
        if (!isset($visited[$neighbour])) {
            dfs($neighbour, $array, $visited, $recStack, $stack, $cycles);
        } elseif ($recStack[$neighbour]) {
            // Мы нашли цикл
            $cycleStartIndex = array_search($neighbour, $stack);
            if ($cycleStartIndex !== false) {
                $cycles[] = array_slice($stack, $cycleStartIndex);
            }
        }
    }

    // Убираем узел из рекурсивного стека
    array_pop($stack);
    $recStack[$node] = false;
}

$array = [
    385 => 392,
    386 => 392,
    387 => 392,
    390 => 402,
    402 => 421,
    405 => 401,
    409 => 416,
    410 => 401,
    414 => 402,
    416 => 389,
    420 => 421,
    421 => 422,
    422 => 420,
];

$cycles = findCycles($array);
print_r($cycles);
```

### Как работает данный код:
1. **Функция `findCycles`**: Инициализирует массивы для отслеживания посещенных узлов и узлов, находящихся на текущем пути, а затем для каждого узла запускает DFS, если он еще не был посещен.
   
2. **Функция `dfs`**: Выполняет рекурсивный обход графа:
   - Отмечает узел как посещенный и добавляет его в стек текущего пути.
   - Если существует соседний узел, который не был посещен, рекурсивно вызывает `dfs` для него.
   - Если находит узел, который уже находится в текущем пути (`recStack`), это означает, что найден цикл. В этом случае сохраняет все узлы цикла.
   - Удаляет узел из стека текущего пути, отмечая его как неактивный для дальнейшей рекурсии.

### Замечания:
- Этот подход сможет выявить все зацикленные цепочки, включая их длину и содержание.
- Учтите, что данная реализация может находить один и тот же цикл несколько раз, если цикл пересекается с другими путями, поэтому при необходимости можно доработать логику для устранения повторяющихся циклов.

Answer 2

не совсем понятно зачем там рекурсия 
 $i = 0;
foreach ($array as $key => $value) {
    $arrayTail = array_slice($array, $i + 1);
    if (in_array($key, $arrayTail)) {
         // зацикливание
    }
    $i++;
}