PHP で隣接行列グラフの幅と深さ優先の走査を実装する方法 (コード)

この記事の内容は、PHP で隣接行列グラフの幅優先トラバーサルと深さ優先トラバーサル (コード) を実装する方法についてです。一定の参考値があります。必要な友人は参考にしてください。お役に立てれば幸いです。 . .

1. グラフの深さ優先の走査は事前順序の走査に似ており、グラフの幅優先の走査はツリーのレベル順の走査に似ています。 . グラフを変形し、頂点と辺の関係に従って階層的に分割し、キューを使用します。トラバースするには
3. 幅優先トラバーサルの重要なポイントは、キューを使用して次のレベルの関連点をすべて格納することです。現在のノードの幅優先走査を順番に実行します。

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

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)

物理的な実装グラフの保存方法:

隣接行列隣接リンクリストクロスリンクリスト隣接多重テーブル

有向グラフの保存方法:クロスリンクリスト

##無向グラフの保存最適化:隣接多重テーブル

グラフの走査:

1. グラフ内の特定の頂点から、グラフ内の残りの頂点への訪問を開始し、各頂点への訪問を 1 回だけ行います

2。訪問した頂点をマークし、配列 Visited[n] を設定し、訪問後に 1 に設定します

3. トラバース順序: 深さ優先トラバーサルと幅優先トラバーサル

深さ優先トラバーサル DFS:

1. 迷路を歩く右手の法則と同様に、1 つのステップをマークし、それが繰り返されるまで右に進み続けます。前の頂点に戻ります。

2. 特定の頂点から開始します。 v と同じパスで頂点にアクセスし、再帰的に

<?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"
}

を呼び出します。

以上がPHP で隣接行列グラフの幅と深さ優先の走査を実装する方法 (コード)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。