PHP의 최소 스패닝 트리 알고리즘에 대한 자세한 설명

PHP의 최소 스패닝 트리 알고리즘에 대한 자세한 설명

최소 스패닝 트리(줄여서 MST)는 연결된 그래프의 최소 가중치 가장자리를 선택하는 문제를 해결하는 데 사용되는 그래프 이론의 중요한 개념입니다. PHP 언어에서는 몇 가지 고전적인 최소 스패닝 트리 알고리즘을 통해 이 함수를 구현할 수 있습니다. 이 기사에서는 일반적으로 사용되는 두 가지 최소 스패닝 트리 알고리즘인 Prim의 알고리즘과 Kruskal의 알고리즘을 자세히 소개하고 해당 PHP 코드 예제를 제공합니다.

1. 프림 알고리즘

프림 알고리즘은 정점에서 시작하여 점차 확장되어 최소 신장 트리를 생성하는 그리디 알고리즘입니다. 구체적인 프로세스는 다음과 같습니다.

1. 시작 정점을 선택하고 선택한 세트에 추가합니다.
2. 현재 선택한 정점 세트에 인접한 정점 중에서 가중치가 가장 작은 가장자리를 선택하여 선택한 가장자리 세트에 추가합니다.
3. 이 가장자리로 연결된 정점을 선택한 정점 세트에 추가합니다.
4. 모든 정점이 선택한 세트에 추가될 때까지 2단계와 3단계를 반복합니다.
5. 최종 모서리 세트는 최소 스패닝 트리입니다.

다음은 Prim의 알고리즘을 PHP에서 구현하기 위한 코드 예제입니다.

function prim($graph) {
    $numVertices = count($graph);
    $selected = array_fill(0, $numVertices, false); // 记录已选择的顶点
    $parent = array_fill(0, $numVertices, -1); // 记录最小生成树的父节点

    $selected[0] = true; // 从第一个顶点开始
    $minWeight = 0;

    for ($i = 0; $i < $numVertices - 1; $i++) {
        $minKey = -1;
        $minVal = PHP_INT_MAX;
        
        for ($j = 0; $j < $numVertices; $j++) {
            if ($selected[$j] == false && $graph[$i][$j] < $minVal) {
                $minKey = $j;
                $minVal = $graph[$i][$j];
            }
        }

        $selected[$minKey] = true;
        $parent[$minKey] = $i;
        $minWeight += $minVal;
    }

    return $minWeight;
}

2. Kruskal 알고리즘

Kruskal 알고리즘은 모든 Edge를 작은 것부터 큰 것까지 가중치별로 정렬한 다음 추가합니다. 스패닝 트리에서는 추가된 에지가 순환을 형성하지 않으면 최소 스패닝 트리의 에지 세트에 추가됩니다. 구체적인 단계는 다음과 같습니다.

1. 모든 가장자리를 무게에 따라 작은 것부터 큰 것까지 정렬합니다.
2. 가중치가 가장 작은 가장자리부터 시작하여 스패닝 트리의 가장자리 세트에 하나씩 추가합니다.
3. 추가된 Edge가 순환을 형성하지 않는 경우 최소 스패닝 트리에 Edge를 추가합니다.
4. 스패닝 트리의 가장자리 수가 정점 수에서 1을 뺀 값과 같아질 때까지 2단계와 3단계를 반복합니다.
5. 최종 모서리 세트는 최소 스패닝 트리입니다.

다음은 PHP에서 Kruskal 알고리즘을 구현하기 위한 코드 예제입니다.

function find($parent, $i) {
    if ($parent[$i] == -1) {
        return $i;
    }

    return find($parent, $parent[$i]);
}

function union($parent, $x, $y) {
    $xSet = find($parent, $x);
    $ySet = find($parent, $y);

    $parent[$xSet] = $ySet;
}

function kruskal($edges, $numVertices) {
    $parent = array_fill(0, $numVertices, -1);
    $minWeight = 0;

    usort($edges, function ($a, $b) {
        return $a['weight'] - $b['weight'];
    });

    $e = 0; // 记录生成树的边数
    $i = 0;

    while ($e < $numVertices - 1) {
        $nextEdge = $edges[$i++];

        $x = find($parent, $nextEdge['src']);
        $y = find($parent, $nextEdge['dest']);

        if ($x != $y) {
            $minWeight += $nextEdge['weight'];
            union($parent, $x, $y);
            $e++;
        }
    }

    return $minWeight;
}

요약:

이 문서에서는 PHP에서 두 가지 최소 스패닝 트리 알고리즘의 원리와 구현 코드를 자세히 설명합니다. Prim의 알고리즘과 Kruskal의 알고리즘은 각각 서로 다른 탐욕 전략을 채택하고 연결 그래프의 최소 신장 트리를 효율적으로 풀 수 있습니다. 이 글이 독자들이 PHP의 최소 스패닝 트리 알고리즘 적용을 이해하는 데 도움이 되기를 바랍니다.

위 내용은 PHP의 최소 스패닝 트리 알고리즘에 대한 자세한 설명의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!