PHP’de Veri yapıları ve algoritmalar 2

Daha detaylı ve ileri düzey algoritma örnekleriyle devam edelim. Bu örneklerde hem karmaşıklığı artıracağız hem de daha gelişmiş veri yapıları ve algoritmalar kullanacağız. Örnekler, daha optimize ve işlevsel algoritmalarla, gerçek hayatta sıkça karşılaşılan sorunlara yönelik olacak.

1. Dijkstra Algoritması (En Kısa Yol Algoritması)

Dijkstra algoritması, bir grafikteki belirli bir düğümden diğer tüm düğümlere olan en kısa yolları bulmak için kullanılır. Genellikle ağırlıklı (weighted) grafikte kullanılır.

<?php
class Graph {
    private $graph;
    private $nodes;


    public function __construct($nodes) {
        $this->graph = [];
        $this->nodes = $nodes;


        foreach ($nodes as $node) {
            $this->graph[$node] = [];
        }
    }


    public function addEdge($start, $end, $weight) {
        $this->graph[$start][$end] = $weight;
        $this->graph[$end][$start] = $weight;  // Eğer çift yönlü ise
    }


    public function dijkstra($start) {
        $distances = [];
        $visited = [];
        $previous = [];
        $pq = new SplPriorityQueue();


        foreach ($this->nodes as $node) {
            $distances[$node] = INF; // Sonsuz
            $previous[$node] = null;
        }


        $distances[$start] = 0;
        $pq->insert($start, 0);


        while (!$pq->isEmpty()) {
            $currentNode = $pq->extract();


            if (isset($visited[$currentNode])) {
                continue;
            }


            $visited[$currentNode] = true;


            foreach ($this->graph[$currentNode] as $neighbor => $weight) {
                $alt = $distances[$currentNode] + $weight;
                if ($alt < $distances[$neighbor]) {
                    $distances[$neighbor] = $alt;
                    $previous[$neighbor] = $currentNode;
                    $pq->insert($neighbor, -$alt); // PriorityQueue’da negatif olarak koyarız çünkü küçük değerler öne çıkar
                }
            }
        }


        return [$distances, $previous];
    }
}


$nodes = ['A', 'B', 'C', 'D', 'E', 'F'];
$graph = new Graph($nodes);


$graph->addEdge('A', 'B', 4);
$graph->addEdge('A', 'C', 2);
$graph->addEdge('B', 'C', 5);
$graph->addEdge('B', 'D', 10);
$graph->addEdge('C', 'E', 3);
$graph->addEdge('E', 'D', 4);
$graph->addEdge('E', 'F', 6);
$graph->addEdge('D', 'F', 11);


list($distances, $previous) = $graph->dijkstra('A');


echo "A'dan diğer düğümlere olan en kısa mesafeler:\n";
foreach ($distances as $node => $distance) {
    echo "$node: $distance\n";
}
?>

2. Kuyruk (Queue) Veri Yapısı ve Genişlik Öncelikli Arama (Breadth-First Search - BFS)

Kuyruk (Queue), FIFO (First-In-First-Out) prensibiyle çalışan bir veri yapısıdır. BFS, genellikle ağaç ve graf yapılarında bir düğümden başlayarak tüm düğümleri seviyeler halinde ziyaret eder.

<?php
class Queue {
    private $queue = [];


    public function enqueue($item) {
        array_push($this->queue, $item);
    }


    public function dequeue() {
        return array_shift($this->queue);
    }


    public function isEmpty() {
        return empty($this->queue);
    }
}


class Graph {
    private $adjList;


    public function __construct($nodes) {
        $this->adjList = [];


        foreach ($nodes as $node) {
            $this->adjList[$node] = [];
        }
    }


    public function addEdge($start, $end) {
        $this->adjList[$start][] = $end;
        $this->adjList[$end][] = $start; // Çift yönlü grafik
    }


    public function bfs($start) {
        $visited = [];
        $queue = new Queue();
        $visited[$start] = true;
        $queue->enqueue($start);


        while (!$queue->isEmpty()) {
            $node = $queue->dequeue();
            echo $node . " ";


            foreach ($this->adjList[$node] as $neighbor) {
                if (!isset($visited[$neighbor])) {
                    $visited[$neighbor] = true;
                    $queue->enqueue($neighbor);
                }
            }
        }
    }
}


$nodes = ['A', 'B', 'C', 'D', 'E', 'F'];
$graph = new Graph($nodes);


$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'D');
$graph->addEdge('B', 'E');
$graph->addEdge('C', 'F');


echo "BFS Ziyaret Sırası: ";
$graph->bfs('A');
?>

3. Merge Sort (Gelişmiş Sıralama Algoritması)

Merge Sort algoritması, büyük bir diziyi küçük alt dizilere ayırır, her birini sıralar ve ardından sıralı bir şekilde birleştirir. Bu algoritma O(n log n) karmaşıklığa sahiptir.

<?php
function mergeSort($arr) {
    if (count($arr) <= 1) {
        return $arr;
    }


    $mid = floor(count($arr) / 2);
    $left = array_slice($arr, 0, $mid);
    $right = array_slice($arr, $mid);


    $left = mergeSort($left);
    $right = mergeSort($right);


    return merge($left, $right);
}


function merge($left, $right) {
    $result = [];
    $i = 0;
    $j = 0;


    while ($i < count($left) && $j < count($right)) {
        if ($left[$i] < $right[$j]) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }


    return array_merge($result, array_slice($left, $i), array_slice($right, $j));
}


$arr = [38, 27, 43, 3, 9, 82, 10];
$sortedArray = mergeSort($arr);


echo "Sıralı Dizi: " . implode(", ", $sortedArray);
?>