Algartam Cuardaigh Graf a Iniúchadh (Graph Search) i PHP

Is teicníocht shuntasach é an t-algartam Cuardaigh Grafa i ríomhchlárú PHP a úsáidtear chun cosáin nó naisc idir rinn i ngraf a aimsiú. Tá sé seo úsáideach go háirithe nuair is gá duit cuardach a dhéanamh ar an gcosán is giorra, ar an nascacht, nó ar an ngaol is lú a bheith ann laistigh de shonraí arna léiriú ag struchtúr graf.

Conas a Oibríonn Algartam Cuardaigh Grafa

Is éard a bhíonn i gceist leis an algartam Cuardach Grafa de ghnáth ná reanna agus imill ghraif a thrasnú chun faisnéis shonrach a chuardach.

1. Ag tosú ó Vertex Foinse: Tosaíonn an t-algartam ag rinn foinse agus trasnaíonn sé trí rinn in aice láimhe trí imill chun cuardach a dhéanamh ar rinn nó cosán ceann scríbe atá ag teastáil.
2. Cuardach Leathan-Chéad(BFS) nó Cuardach Doimhneachta-An Chéad(DFS): Tá dhá phríomh-chur chuige don algartam seo: Cuardach Leathan-Chéad(BFS) agus Doimhneacht-An Chéad Chuardach(DFS). Déanann BFS cuardach ar rinn in aice láimhe sula mbogann sé go dtí an chéad leibhéal eile, agus déanann DFS iniúchadh níos doimhne isteach i mbrainse sula ndéantar cúlrianú.
3. Vertex Ceann Scríbe á Seiceáil: Seiceálann an algartam an bhfuil an rinn nó an gaol cinn scríbe inmhianaithe ann. Má aimsítear é, filleann an t-algartam an toradh nó an cosán cuí.

Buntáistí agus Míbhuntáistí Algartam Cuardaigh Graf

Buntáistí:

• Nascacht agus Pathfinding: Cuidíonn an algartam seo le naisc nó cosáin a aimsiú idir rinn i ngraf.
• Aimsiú Conair Is Giorra: Nuair a bhíonn athróg faid á úsáid agat, is féidir leis an algartam an cosán is giorra idir na rinn a chinneadh.

Míbhuntáistí:

• Feidhmíocht ag brath ar Struchtúr Grafa: Braitheann feidhmíocht an algartam ar struchtúr agus ar mhéid an ghraif.
• Cumas Cuardach Teoranta: D’fhéadfadh go mbeadh teorainn leis an algartam agus tú ag déileáil le graif mhóra agus chasta.

Sampla agus Míniú

Samhlaigh go bhfuil líonra sóisialta agat le húsáideoirí agus a gcaidrimh léirithe mar ghraf. Ba mhaith leat a chinneadh an bhfuil nasc idir úsáideoir A agus úsáideoir B. Seo sampla de conas is féidir leat algartam cuardaigh graf a chur i bhfeidhm i 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.";  
}  

Sa sampla seo, tógaimid líonra sóisialta fíorúil ag baint úsáide as eagar chun cuardach a dhéanamh ar chonair idir dhá úsáideoir laistigh den líonra a insamhail. Bainimid úsáid as an modh Breadth-First Search(BFS) chun trasnú trí rinn agus imill chun nasc a aimsiú idir úsáideoir A agus úsáideoir B. Má aimsítear nasc, filleann an algartam an toradh go bhfuil gaol idir an dá úsáideoir; ar shlí eile, tuairiscíonn sé nach bhfuil aon ghaol ann.

Cé go léiríonn an sampla seo algartam cuardaigh graf simplí, i ndáiríre, is féidir halgartaim chuardaigh graf a chur i bhfeidhm go forleathan chun naisc, na cosáin is giorra, agus feidhmchláir éagsúla eile i ríomhchlárú PHP a aimsiú.