dijkstra算法 PHP 实现

20171119 利用周末优化了一下代码。这次完全默写了出来。感觉好多了

这个是根据算法图解自己写的,理解的不是很好,注释都在代码里面,过几天再默写一下,好好理解一下

<?php

// 构造图
$graphs = [];
$graphs['start'] = [];
$graphs['start']['a'] = 5;
$graphs['start']['b'] = 2;

$graphs['a'] = [];
$graphs['a']['c'] = 4;
$graphs['a']['d'] = 2;

$graphs['b'] = [];
$graphs['b']['a'] = 8;
$graphs['b']['d'] = 7;

$graphs['c'] = [];
$graphs['c']['d'] = 6;
$graphs['c']['fin'] = 3;

$graphs['d'] = [];
$graphs['d']['fin'] = 1;

$graphs['fin'] = [];

// 处理过的节点
$processed = [];
// 所有节点的消费
$costs = [];
// 所有节点的父节点
$parents = [];

function getNodeCost($graphs, $nodeName = 'start', $isStartNode = false)
{
    if (empty($graphs)) {
        return [];
    }
    $costs = [];
    foreach ($graphs[$nodeName] as $name => $length) {
        if ($isStartNode) {
            $costs[$name] = $length;
        } else {
            $costs[$name] = INF;
        }
        $costs += getNodeCost($graphs, $name);
    }

    return $costs;
}

$costs = getNodeCost($graphs, 'start', true);

function getNodeParents($graphs, $nodeName = 'start', $isStartNode = false)
{
    if (empty($graphs)) {
        return [];
    }
    $parents = [];
    foreach ($graphs[$nodeName] as $name => $length) {
        if ($isStartNode) {
            $parents[$name] = $nodeName;
        } else {
            $parents[$name] = null;
        }
        $parents += getNodeParents($graphs, $name);
    }

    return $parents;
}

$parents = getNodeParents($graphs, 'start', true);

function findLowestCostNode($costs, $processed)
{
    $lowestNodeLength = INF;
    $lowestNOdeName = '';
    foreach ($costs as $name => $length) {
        if ($length < $lowestNodeLength && !in_array($name, $processed)) {
            $lowestNodeLength = $length;
            $lowestNOdeName = $name;
        }
    }

    return $lowestNOdeName;
}

$nodeName = findLowestCostNode($costs, $processed);
while ($nodeName) {
    $currentNodeCost = $costs[$nodeName];
    foreach ($graphs[$nodeName] as $name => $length) {
        if ($currentNodeCost + $length < $costs[$name]) {
            $costs[$name] = $currentNodeCost + $length;
            $parents[$name] = $nodeName;
        }
    }
    $processed[] = $nodeName;
    $nodeName = findLowestCostNode($costs, $processed);
}

var_dump($costs);
var_dump($parents);

广度优先搜索 PHP 实现

直接上代码了,注释都在代码里面了。

<?php
/**
 * 广度搜索
 *
 * 你的朋友关系,以及朋友的朋友的关系,查看你的朋友或者朋友的朋友是不是包含 m 结尾的名字
 */

// 需要检索的数组
$graph = [];
$graph['you'] = ['alice', 'bob', 'claire'];
$graph['bob'] = ['anuj', 'peggy'];
$graph['alice'] = ['peggy'];
$graph['claire'] = ['thom', 'jonny'];
$graph['anuj'] = [];
$graph['peggy'] = [];
$graph['thom'] = [];
$graph['jonny'] = [];

// 搜索过的数组
$searchedItem = [];
// 待检索的数组
$waitSearchArray = [];
// 将第一层的关系加入到等待搜索的数组
$waitSearchArray = array_merge($waitSearchArray, $graph['you']);

// 将结果元素赋值为 false
$resultName = false;

//需要查找的字符
$findChar = 'z';

// 如果等待搜索的数组不为空就循环查找
while ($waitSearchArray) {
    // 从队列头部弹出一个元素
    $name = array_shift($waitSearchArray);
    // 如果待检查的元素在已经搜索过的数组中,就跳过,这个是用来防止循环检查的
    if (in_array($name, $searchedItem)) {
        continue;
    }
    // 获取最后一个字符
    $lastChar = substr($name, strlen($name) - 1, 1);
    // 如果最后一个字符是 m,就说明找到了,把结果赋值,然后跳出循环
    if ($lastChar == $findChar) {
        $resultName = $name;
        break;
    }

    // 到这里了说明没有找到,那么把这个人的名字,放入到已经搜索过的数组中
    $searchedItem[] = $name;
    // 然后再把这个名字的朋友关系加入到待搜索的数组中
    $waitSearchArray = array_merge($waitSearchArray, $graph[$name]);
}

var_dump($resultName);