46 lines
1.1 KiB
PHP
46 lines
1.1 KiB
PHP
|
<?php
|
||
|
|
|
||
|
|
namespace Graphp\Algorithms\Search;
|
||
|
|
|
||
|
|
use Fhaculty\Graph\Vertex;
|
||
|
|
use Fhaculty\Graph\Graph;
|
||
|
|
use Fhaculty\Graph\Set\Vertices;
|
||
|
|
|
||
|
|
class BreadthFirst extends Base1
|
||
|
|
{
|
||
|
|
/**
|
||
|
|
*
|
||
|
|
* @return Vertices
|
||
|
|
*/
|
||
|
|
public function getVertices()
|
||
|
|
{
|
||
|
|
$queue = array($this->vertex);
|
||
|
|
// to not add vertices twice in array visited
|
||
|
|
$mark = array($this->vertex->getId() => true);
|
||
|
|
// visited vertices
|
||
|
|
$visited = array();
|
||
|
|
|
||
|
|
do {
|
||
|
|
// get first from queue
|
||
|
|
$t = array_shift($queue);
|
||
|
|
// save as visited
|
||
|
|
$visited[$t->getId()]= $t;
|
||
|
|
|
||
|
|
// get next vertices
|
||
|
|
foreach ($this->getVerticesAdjacent($t)->getMap() as $id => $vertex) {
|
||
|
|
// if not "touched" before
|
||
|
|
if (!isset($mark[$id])) {
|
||
|
|
// add to queue
|
||
|
|
$queue[] = $vertex;
|
||
|
|
// and mark
|
||
|
|
$mark[$id] = true;
|
||
|
|
}
|
||
|
|
}
|
||
|
|
|
||
|
|
// untill queue is empty
|
||
|
|
} while ($queue);
|
||
|
|
|
||
|
|
return new Vertices($visited);
|
||
|
|
}
|
||
|
|
}
|