So implementieren Sie die Breiten- und Tiefendurchquerung des Adjazenzmatrixdiagramms in PHP (Code)

Der Inhalt dieses Artikels befasst sich mit der Implementierung des Breiten- und Tiefendurchlaufs (Code) eines Adjazenzmatrixdiagramms. Ich hoffe, dass er für Sie hilfreich ist . .

1. Die Tiefendurchquerung des Diagramms ähnelt der Vorordnungsdurchquerung, und die Breitendurchquerung des Diagramms ähnelt der Ebenenreihenfolge-Durchquerung des Baums
2. Verformen Sie den Graphen, teilen Sie ihn hierarchisch entsprechend der Beziehung zwischen Scheitelpunkten und Kanten auf und verwenden Sie Warteschlangen. Zum Durchlaufen
3. Der Schlüsselpunkt der Breitendurchquerung besteht darin, eine Warteschlange zum Speichern aller zugeordneten Punkte der nächsten Ebene zu verwenden aktuellen Knoten und führen Sie dann die Breite-zuerst-Durchquerung der Adjazenzmatrix

in der Reihenfolge durch:

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)      //此顶点入队列,会排在后面等前面一层的全遍历完才会遍历这个

Tiefen-zuerst-Durchquerung von 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)

Implementierung der physischen Speicherung von Diagrammen:

Adjazenzmatrix-Adjazenz-verknüpfte Liste, vernetzte Liste, Adjazenz-Mehrfachliste

Gerichtete Diagrammspeichermethode: vernetzte Liste

Optimierung der ungerichteten Diagrammspeicherung : benachbarte Mehrfachliste

Diagrammdurchquerung:

1. Von einem bestimmten Scheitelpunkt im Diagramm aus beginnen Sie, die verbleibenden Scheitelpunkte im Diagramm zu besuchen und jeden Scheitelpunkt nur einmal zu besuchen
2. Sie Sie müssen die besuchten Scheitelpunkte markieren, ein Array besuchte[n] festlegen und es nach dem Besuch auf 1 setzen
3. Durchquerungsreihenfolge: Durchquerung der Tiefe zuerst und Durchquerung der Breite zuerst

Durchquerung der Tiefe zuerst DFS:

1. Markieren Sie ähnlich wie bei der Rechtshand-Regel beim Gehen in einem Labyrinth einen Schritt und gehen Sie weiter nach rechts, bis er wiederholt wird. Kehren Sie zum vorherigen Scheitelpunkt zurück
2. Beginnen Sie bei a Bestimmter Scheitelpunkt v, um auf den Scheitelpunkt mit einem mit v verbundenen Pfad zuzugreifen und rekursiv

<?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);

array(5) {
  [0]=>
  string(2) "V0"
  [1]=>
  string(2) "V4"
  [2]=>
  string(2) "V1"
  [3]=>
  string(2) "V2"
  [4]=>
  string(2) "V3"
}
array(5) {
  [0]=>
  string(2) "V1"
  [1]=>
  string(2) "V0"
  [2]=>
  string(2) "V4"
  [3]=>
  string(2) "V2"
  [4]=>
  string(2) "V3"
}

aufzurufen

Das obige ist der detaillierte Inhalt vonSo implementieren Sie die Breiten- und Tiefendurchquerung des Adjazenzmatrixdiagramms in PHP (Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!