当前位置: 首页 > article >正文

PHP中实现拓扑算法

概念

拓扑算法是一个有向无线算法
是一个处理复杂关系的算法

应用场景

A = B+C
B = C+D
C = A+T
这里的值因为计算顺序不同,会导致计算结果不同,而拓扑排序就能解决这个问题,找出先计算那一位

环的概念

拓扑排序中的一个bug
如果
A =B+C
B = C+D
C = A+D
这里A的值会影响C,C会影响A,所以一旦出现这种情况即预示着出现了环,该逻辑有问题

代码示例

//假设数据结构是这样的
public function text(){
        $accounts = [
            ['name' => 'A', 'value' => "C + B"],
            ['name' => 'B', 'value' => "C + D"],
            ['name' => 'C', 'value' => 100],
            ['name' => 'D', 'value' => 100],
            ['name' => 'E', 'value' => "A + B + C"],
        ];

        $initialValues = [
            'C' => 100,
            'D'=> 100,
        ];

$analysister_config_data = $this->calculateAccountBalances($accounts,$initialValues);
return['data'=>$analysister_config_data ];
}




 /**
     * @param $accounts
     * @param $initial_values
     * @return array
     * 用于计算所有所有账户最终余额
     */
    function calculateAccountBalances($accounts, $initialValues) {
        $graph = $this->buildDependencyGraph($accounts);
        $sortedNodes = $this->topologicalSort($graph);

        $balances = $initialValues;
        foreach ($sortedNodes as $node) {
            if (isset($balances[$node])) {
                continue;
            }
            // 获取当前节点的表达式
            $expression = $accounts[array_search($node, array_column($accounts, 'name'))]['value'];
            // 替换表达式中的变量为已知值
            foreach ($balances as $key => $value) {
                $expression = str_replace($key, $value, $expression);
            }
            // 计算表达式的值
            $balances[$node] = eval("return $expression;");
        }

        return $balances;
    }




/**
     * @param $value:当前账户的值,
     * @param $accountValues:一个引用数组,存储已经计算的值避免重复计算
     * @param $accounts:所有账户
     * @return int*
     */
    function parseValue($value, &$accountValues, $accounts, $initialValues) {
        $parts = explode(' ', $value);
        $result = 0;
        $operator = '+';

        foreach ($parts as $part) {
            if ($part === '+' || $part === '-') {
                $operator = $part;
                continue;
            }

            if (ctype_alnum($part)) { // 只处理有效的账户名称
                if (isset($accountValues[$part])) {
                    $value = $accountValues[$part];
                } elseif (isset($initialValues[$part])) {
                    $value = $initialValues[$part];
                    $accountValues[$part] = $value; // 确保将初始值存储到 accountValues 中
                } else {
                    if (isset($accounts[$part])) {
                        $value = $this->parseValue($accounts[$part]['value'], $accountValues, $accounts, $initialValues);
                    } else {
                        echo ("账户没找到 " . $part);
                    }
                }
            } else {
                // 如果 part 是数字,直接使用
                $value = (int)$part;
            }

            if ($operator === '+') {
                $result += $value;
            } else {
                $result -= $value;
            }
        }

        return $result;
    }


 /**
     * @param $accounts
     * @return array
     * 将需要计算的数据生成为依赖关系图
     */
    function buildDependencyGraph($accounts) {
        $graph = [];
        foreach ($accounts as $account) {
            $name = $account['name'];
            if (!isset($graph[$name])) {
                $graph[$name] = [];
            }
            $parts = explode(' ', $account['value']);
            foreach ($parts as $part) {
                if (is_numeric($part)){
                    continue;
                }
                if (ctype_alnum($part) && !in_array($part, ['+', '-'])) {
                    $graph[$name][] = $part;
                    if (!isset($graph[$part])) {
                        $graph[$part] = [];
                    }
                }
            }
        }
        return $graph;
    }

    /**
     * @param $graph 依赖图,是一个二维数组,表示依赖关系
     * @return array
     * 用于对数据排序,按照依赖关系排序
     */
    function topologicalSort($graph) {
        $inDegree = []; // 节点的入度
        $zeroDegree = []; // 入度为0的节点
        $sorted = []; // 拓扑排序结果

        // 初始化所有节点的入度为0
        foreach ($graph as $node => $dependencies) {
            $inDegree[$node] = 0;
        }

        // 计算每个节点的入度
        foreach ($graph as $node => $dependencies) {
            foreach ($dependencies as $dependency) {
                if (ctype_alnum($dependency)) { // 确保只处理有效的账户名称
                    if (!isset($inDegree[$dependency])) {
                        $inDegree[$dependency] = 0; // 确保所有节点都在 inDegree 数组中
                    }
                    $inDegree[$node]++; // 这里应该增加当前节点的入度
                }
            }
        }

        // 找出入度为0的节点
        foreach ($inDegree as $node => $degree) {
            if ($degree == 0) {
                $zeroDegree[] = $node;
            }
        }

        // 进行拓扑排序
        while (!empty($zeroDegree)) {
            $node = array_shift($zeroDegree);
            $sorted[] = $node;


            // 处理当前节点的依赖关系
            foreach ($graph as $currentNode => $dependencies) {
                if (in_array($node, $dependencies)) {
                    $inDegree[$currentNode]--;
                    if ($inDegree[$currentNode] == 0) {
                        $zeroDegree[] = $currentNode;
                    }
                }
            }
        }

        // 检测是否存在环
        if (count($sorted) != count($graph)) {
            echo '存在环,无法进行拓扑排序';
        }
        return $sorted;
    }


http://www.kler.cn/a/448730.html

相关文章:

  • 北京中小学信息学编程能力测评 BCSP-X 2024 下半年 真题汇总
  • JAVA:组合模式(Composite Pattern)的技术指南
  • 多模态医学图像融合概述
  • 【Windows版】opencv 和opencv_contrib配置
  • UIP协议栈 TCP通信客户端 服务端,UDP单播 广播通信 example
  • 线性代数期末总复习的点点滴滴(1)
  • Bazel CI
  • 基于 SSM 和 Vue 的 WEB 开放性实验室集成管理系统
  • 【leetcode100】排序链表
  • springboot根据租户id动态指定数据源
  • react Moment.js 是一个流行的 JavaScript 库,用于处理日期和时间。它提供了丰富的功能,包括日期格式化、解析、操作和国际化
  • 前端 下载文件时如何处理后端返回的 文件流
  • Vulkan 学习(10)---- Vulkan SwapChain 创建
  • 实现 React 电子签名功能:从零开始构建一个完整的解决方案
  • Unity全局雾效
  • 深度学习革新音乐转录
  • MQTT实现集群分布式消费
  • 计算机前沿技术-人工智能算法-大语言模型-最新研究进 2024-12-22
  • XRP价格跌破2.20美元 1.94美元是否下一波牛市的关键支撑?
  • 【再谈设计模式】外观模式~复杂系统交互的简化大师
  • 0.gitlab ubuntu20.04 部署问题解决
  • 理解并使用Linux 内核中的 Tracepoint
  • C++ 基本语法
  • jenkins启动脚本,jar包自动化启动脚本
  • 如何解决微信小程序使用webview无法打开
  • Windows系统中使用git常见问题解决方案