README

fisharebest/algorithm

PHP中的通用算法

• Dijkstra算法
• Myers差异算法
• 图的连通/不连通组件

安装

使用composer安装。

composer require fisharebest/algorithm

Dijkstra算法

Dijkstra算法 用于在加权、有向图中找到两个节点之间的最短路径。

图被指定为一个边的数组，每个边都有一个成本。下面的示例是一个无向图（即如果D→E是9，那么E→D也是9），因为它易于理解且易于绘制。然而，该算法对于有向图同样有效，其中链接可以是单向的或者每个方向有不同的成本。

     D---9---E
    / \       \
  14   2       6
  /     \       \
 A---9---B--11--C
  \     /      /
   7  10      /
    \ /      /
     F-----15       G

上述图的示例代码。

$graph = array(
  'A' => array('B' => 9, 'D' => 14, 'F' => 7),
  'B' => array('A' => 9, 'C' => 11, 'D' => 2, 'F' => 10),
  'C' => array('B' => 11, 'E' => 6, 'F' => 15),
  'D' => array('A' => 14, 'B' => 2, 'E' => 9),
  'E' => array('C' => 6, 'D' => 9),
  'F' => array('A' => 7, 'B' => 10, 'C' => 15),
  'G' => array(),
);

$algorithm = new \Fisharebest\Algorithm\Dijkstra($graph);

// There can be zero, one or more shortest (i.e. same total cost) paths.

// No shortest path.
$path = $algorithm->shortestPaths('A', 'G'); // array()

// Exactly one shortest path.
$path = $algorithm->shortestPaths('A', 'E'); // array(array('A', 'B', 'D', 'E'))

// Multiple solutions with the same shortest path.
$path = $algorithm->shortestPaths('E', 'F'); // array(array('E', 'D', 'B', 'F'), array('E', 'C', 'F'))

// To find next-shortest paths, exclude one or more intermediate nodes from the shortest path.
$path = $algorithm->shortestPaths('A', 'E'); // array(array('A', 'B', 'D', 'E'))
$path = $algorithm->shortestPaths('A', 'E', array('B')); // array(array('A', 'B', 'D', 'E'))
$path = $algorithm->shortestPaths('A', 'E', array('D')); // array(array('A', 'B', 'C', 'E'))
$path = $algorithm->shortestPaths('A', 'E', array('B', 'D')); // array(array('A', 'F', 'C', 'E'))

Myers差异算法

使用Eugene W. Myers的“一个O(ND)差异算法及其变体”找到两个标记序列（字符、单词、行等）之间的差异。

输出可以解释为

• 一系列将第一个序列转换为第二个序列的指令。
• 匹配列表（出现在两个序列中的标记）和失配列表（仅出现在一个序列中的标记）。

$x = array('a', 'b', 'c', 'a', 'b', 'b', 'a');
$y = array('c', 'b', 'a', 'b', 'a', 'c');
$algorithm = new MyersDiff;
$diff = $algorithm->calculate($x, $y);
// array(
//  array('a', MyersDiff::DELETE),   i.e. 'a' occurs only in $x
//  array('b', MyersDiff::DELETE),   i.e. 'b' occurs only in $x
//  array('c', MyersDiff::KEEP),     i.e. 'c' occurs both $x and $y
//  array('b', MyersDiff::INSERT),   i.e. 'b' occurs only in $y
//  array('a', MyersDiff::KEEP),     i.e. 'a' occurs in both $x and $y
//  array('b', MyersDiff::KEEP),     i.e. 'b' occurs in both $x and $y
//  array('b', MyersDiff::DELETE),   i.e. 'b' occurs only in $x
//  array('a', MyersDiff::KEEP),     i.e. 'a' occurs in both $x and $y
//  array('c', MyersDiff::INSERT),   i.e. 'c' occurs only in $y
// );

连通组件

对图进行深度优先搜索以找到孤立的节点组。

    D    E
   / \    \
  /   \    \
 A-----B   C
  \   /
   \ /
    F

上述图的示例代码

$graph = array(
	'A' => array('B' => 1, 'D' => 1, 'F' => 1),
	'B' => array('A' => 1, 'D' => 1, 'F' => 1),
	'C' => array('E' => 1),
	'D' => array('A' => 1, 'B' => 1),
	'E' => array('C' => 1),
	'F' => array('A' => 1, 'B' => 1),
);

$algorithm  = new \Fisharebest\Algorithm\ConnectedComponent($graph);
$components = $algorithm->findConnectedComponents());
// array(
//  1 => array('A', 'B', 'D', 'F'),
//  2 => array('C', 'E'),
// );