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

不言
Freigeben: 2023-04-04 08:20:02
nach vorne
3109 Leute haben es durchsucht

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

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)
Nach dem Login kopieren

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);
Nach dem Login kopieren
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"
}
Nach dem Login kopieren
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!

Verwandte Etiketten:
php
Quelle:cnblogs.com
Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn
Beliebte Tutorials
Mehr>
Neueste Downloads
Mehr>
Web-Effekte
Quellcode der Website
Website-Materialien
Frontend-Vorlage