Detailed explanation of the minimum spanning tree algorithm in PHP

Detailed explanation of the minimum spanning tree algorithm in PHP

The minimum spanning tree (Minimum Spanning Tree, referred to as MST) is an important concept in graph theory, used to solve the problem of selecting the minimum weight edge of a connected graph. In the PHP language, we can implement this function through some classic minimum spanning tree algorithms. This article will introduce in detail two commonly used minimum spanning tree algorithms: Prim's algorithm and Kruskal's algorithm, and give corresponding PHP code examples.

1. Prim algorithm

The Prim algorithm is a greedy algorithm that starts from a vertex and gradually expands to generate a minimum spanning tree. The specific process is as follows:

1. Select a starting vertex and add it to the selected set.
2. Select the edge with the smallest weight from the vertices adjacent to the currently selected vertex set and add it to the selected edge set.
3. Add the vertices connected by this edge to the selected vertex set.
4. Repeat steps 2 and 3 until all vertices have been added to the selected set.
5. The final set of edges is the minimum spanning tree.

The following is a code example for implementing Prim's algorithm in 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 algorithm

Kruskal algorithm is an edge-based greedy algorithm. It first All edges are sorted from small to large in weight, and then added to the spanning tree one by one. If the added edges do not form a cycle, they are added to the edge set of the minimum spanning tree. The specific steps are as follows:

1. Sort all edges by weight from small to large.
2. Start from the edge with the smallest weight and add it to the edge set of the spanning tree one by one.
3. If the added edge does not form a cycle, add the edge to the minimum spanning tree.
4. Repeat steps 2 and 3 until the number of edges in the spanning tree is equal to the number of vertices minus one.
5. The final set of edges is the minimum spanning tree.

The following is a code example for implementing Kruskal's algorithm in PHP:

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;
}

Summary:

This article introduces in detail the principles and principles of two minimum spanning tree algorithms in PHP Implement the code. Prim's algorithm and Kruskal's algorithm respectively adopt different greedy strategies and can efficiently solve the minimum spanning tree of connected graphs. I hope this article will help readers understand the application of the minimum spanning tree algorithm in PHP.

The above is the detailed content of Detailed explanation of the minimum spanning tree algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!