close

Meneroka (Graph Search) Algoritma Carian Graf dalam PHP

Algoritma Carian Graf ialah teknik penting dalam pengaturcaraan PHP yang digunakan untuk mencari laluan atau sambungan antara bucu dalam graf. Ini amat berguna apabila anda perlu mencari laluan terpendek, ketersambungan atau kewujudan perhubungan dalam data yang diwakili oleh struktur graf.

Cara Algoritma Carian Graf Berfungsi

Algoritma Carian Graf biasanya melibatkan merentasi bucu dan tepi graf untuk mencari maklumat tertentu.

  1. Bermula dari Puncak Sumber: Algoritma bermula pada bucu sumber dan merentasi bucu bersebelahan melalui tepi untuk mencari bucu atau laluan destinasi yang diingini.
  2. Breadth-First Search(BFS) atau Depth-First Search(DFS): Terdapat dua pendekatan utama untuk algoritma ini: Breadth-First Search(BFS) dan Depth-First Search(DFS). BFS mencari bucu bersebelahan sebelum beralih ke peringkat seterusnya, manakala DFS meneroka lebih dalam ke dalam cawangan sebelum menjejak ke belakang.
  3. Menyemak Bucu Destinasi: Algoritma menyemak sama ada bucu destinasi yang diingini atau hubungan wujud. Jika ditemui, algoritma mengembalikan hasil atau laluan yang sesuai.

Kelebihan dan Kelemahan Algoritma Carian Graf

Kelebihan:

  • Ketersambungan dan Pencarian Laluan: Algoritma ini membantu dalam mencari sambungan atau laluan antara bucu dalam graf.
  • Pencarian Laluan Terpendek: Apabila menggunakan pembolehubah jarak, algoritma boleh menentukan laluan terpendek antara bucu.

Kelemahan:

  • Prestasi Bergantung pada Struktur Graf: Prestasi algoritma bergantung pada struktur dan saiz graf.
  • Keupayaan Carian Terhad: Algoritma mungkin terhad apabila berurusan dengan graf yang besar dan kompleks.

Contoh dan Penerangan

Bayangkan anda mempunyai rangkaian sosial dengan pengguna dan perhubungan mereka diwakili sebagai graf. Anda ingin menentukan sama ada sambungan wujud antara pengguna A dan pengguna B. Berikut ialah contoh cara anda boleh melaksanakan algoritma carian graf dalam PHP:

$graph = array(  
    'A' => array('B', 'C'),  
    'B' => array('A', 'D'),  
    'C' => array('A', 'E'),  
    'D' => array('B'),  
    'E' => array('C', 'F'),  
    'F' => array('E')  
);  
  
$startNode = 'A';  
$endNode = 'B';  
  
function searchGraph($graph, $start, $end) {  
    $visited = array();  
    $queue = new SplQueue();  
    $queue->enqueue($start);  
  
    while(!$queue->isEmpty()) {  
        $node = $queue->dequeue();  
  
        if(!isset($visited[$node])) {  
            $visited[$node] = true;  
  
            if($node === $end) {  
                return true;  
            }  
  
            foreach($graph[$node] as $neighbor) {  
                if(!isset($visited[$neighbor])) {  
                    $queue->enqueue($neighbor);  
                }  
            }  
        }  
    }  
  
    return false;  
}  
  
if(searchGraph($graph, $startNode, $endNode)) {  
    echo "There is a connection between $startNode and $endNode.";  
} else {  
    echo "There is no connection between $startNode and $endNode.";  
}

Dalam contoh ini, kami membina rangkaian sosial maya menggunakan tatasusunan untuk mensimulasikan pencarian laluan antara dua pengguna dalam rangkaian. Kami menggunakan kaedah Breadth-First Search(BFS) untuk merentasi bucu dan tepi untuk mencari sambungan antara pengguna A dan pengguna B. Jika sambungan ditemui, algoritma mengembalikan hasil bahawa terdapat hubungan antara kedua-dua pengguna; jika tidak, ia melaporkan bahawa tiada hubungan.

Walaupun contoh ini menunjukkan algoritma carian graf yang mudah, sebenarnya, algoritma carian graf boleh digunakan secara meluas untuk mencari sambungan, laluan terpendek dan pelbagai aplikasi lain dalam pengaturcaraan PHP.