Comment implémenter la première traversée en largeur et en profondeur du graphique matriciel de contiguïté en PHP (code)

Le contenu de cet article explique comment implémenter le premier parcours (code) en largeur et en profondeur du graphique matriciel de contiguïté en PHP. Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer. .

1. Le parcours en profondeur d'abord du graphique est similaire au parcours de pré-ordre, et le parcours en largeur d'abord du graphique est similaire au parcours en ordre de niveau de l'arbre
2. Déformez le graphique, divisez-le hiérarchiquement en fonction de la relation entre les sommets et les arêtes et utilisez des files d'attente pour parcourir
3. Le point clé du parcours en largeur d'abord est d'utiliser une file d'attente pour stocker tous les points associés de niveau suivant du nœud actuel, puis effectuez le parcours en largeur d'abord de la matrice de contiguïté

dans l'ordre :

BFS(G)
for i=0;i<G->numVertexes;i++
visited[i]=false;//检测是否访问过
for i=0;i<G.numVertexes;i++//遍历顶点
if visited[i]==true break;//访问过的断掉
visited[i]=true //当前顶点访问
InQueue(i)      //当前顶点入队列
while(!QueueEmpty()) //当前队列不为空
i=OutQueue() //队列元素出队列
for j=0;j<G->numVertexes;j++ //遍历顶点
if G->arc[i][j]==1 && !visited[j] //当前顶点与其他顶点存在关系并且未被访问
visited[j]=true //标记此顶点
InQueue(j)      //此顶点入队列,会排在后面等前面一层的全遍历完才会遍历这个

Parcours en profondeur en premier DFS :

DFSTravserse G
    for i=0;i<G.xNum;i++
        if !visted[i]
            DFS(G,i)
DFS G,i
    visted[i]=true
    print G.vexs[i]
    if G.arc[i][j]==1 && !visited[j]
        DFS(G,j)

Mise en œuvre du stockage physique du graphe :

Matrice de contiguïté liste chaînée liste chaînée croisée liste multiple de contiguïté

Méthode de stockage de graphe dirigé : liste chaînée croisée

Optimisation de stockage de graphiques non orientés : liste multiple de contiguïté

Parcours du graphique :

1 À partir du graphique Commencez à partir d'un certain sommet du graphique et visitez les sommets restants du graphique, et faites en sorte que chaque sommet soit visité uniquement. une fois
2. Vous devez marquer les sommets visités, définir un tableau visité[n] et le définir sur 1 après la visite
3 Ordre de traversée : parcours en profondeur d'abord et parcours en largeur en premier

.

Parcours en profondeur DFS :

1 Semblable à la règle de la main droite de la marche dans un labyrinthe, marquez un pas et continuez vers la droite jusqu'à ce que si cela se répète, revenez au sommet précédent 2. Partez d'un certain sommet v pour visiter le sommet avec un chemin connecté à v, et appelez récursivement

<?php
class Graph{
        public $vertexs;
        public $arc;
        public $num=5;
}
$G=new Graph();
for($i=0;$i<$G->num;$i++){
        $G->vertexs[$i]="V{$i}";
}
$G->arc[1][0]=9;
$G->arc[1][2]=3;
$G->arc[2][0]=2;
$G->arc[2][3]=5;
$G->arc[3][4]=1;
$G->arc[0][4]=6;
//广度优先遍历
function BFS($G){
        $res=array();
        $queue=array();
        for($i=0;$i<$G->num;$i++){
                $visited[$i]=false;
        }   
        for($i=0;$i<$G->num;$i++){
                if($visited[$i]){
                        break;
                }   
                $visited[$i]=true;
                $res[]=$G->vertexs[$i];
                array_push($queue,$i);
                while(!empty($queue)){
                        $v=array_pop($queue);
                        for($j=0;$j<$G->num;$j++){
                                if($G->arc[$v][$j]>0 && !$visited[$j]){
                                        $visited[$j]=true;
                                        $res[]=$G->vertexs[$j];
                                        array_push($queue,$j);
                                }   
                        }   
                }   
        }   
        return $res;
}
//深度优先遍历
function DFS($G,$i){
        static $res;
        static $visited;
        if(!$visited[$i]){
                $visited[$i]=true;
                $res[]=$G->vertexs[$i];
        }
                for($j=0;$j<$G->num;$j++){
                        if($G->arc[$i][$j]>0 && !$visited[$j]){
                                $visited[$j]=true;
                                $res[]=$G->vertexs[$j];
                                DFS($G,$j);
                        }
                }
        return $res;
}
$b=BFS($G);
$d=DFS($G,1);
var_dump($b);
var_dump($d);

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!