php 实现交并集算法

set_union.php

<?php

    $node_arr = array();
    //记录每个单词首次出现的位置
    $word_position = array(); 
    /**
     * 查找当前节点大夫节点 
     */
    function find($node)
    {
        global $node_arr;
        if($node_arr [$node] != $node) 
        {
            $node_arr[$node]  = find($node_arr[$node]);
        }
        return $node_arr[$node];
    }

    function union($node_a, $node_b)
    {
        global $node_arr;
        $fa = find($node_a);
        $fb = find($node_b);
        
        if($fa != $fb)
        {
            //并交集的核心思想是让存在交集的节点
            //的夫节点等于另外一个节点大夫节点
            $node_arr [$fb]  = $fa;
        }
    }

    $groups = array(
        'group_1'  => array(1, 2, 3, 4),   
        'group_2'  => array(7, 8, 9),
        'group_3'  => array(4, 5, 13),
        'group_4'  => array(10, 11, 12, 5),
        'group_5'  => array(6, 1, 17),
        'group_6'  => array(15, 17, 19,12)
    );
    //处理每个节点首次出现的位置,即其所在组
    foreach($groups as $key => $group)
    {
        $node_arr[$key] = $key; 
        foreach($group as $node)
        {
            if(!isset($word_position[$node])) 
            {
                $word_position[$node] = $key;
            }
        }
    }

    foreach($groups AS $key=> $group)
    {
        foreach($group AS $node)
        {
            union($key, $word_position[$node]); 
        }
    }
    //是为了降低树的高度
    foreach($groups AS $key => $group)
    {
        find($key); 
    }
    $node_1 = $argv[1];
    $node_2 = $argv[2];

    foreach($groups as $row)
    {
        echo implode(",", $row)."\n";
    }
    
    if(find($word_position[$node_1]) == find($word_position[$node_2]))
    {
        echo 'same group';
    }
    else
    {
        echo 'no same group';
    }