PHP에서 인접 행렬 그래프의 너비 및 깊이 우선 순회를 구현하는 방법(코드)

이 글의 내용은 PHP에서 인접 행렬 그래프의 폭과 깊이 우선 탐색(코드)을 구현하는 방법에 대한 것입니다. 필요한 친구들이 참고할 수 있기를 바랍니다. .

1. 그래프의 깊이 우선 순회는 선주문 순회와 유사하며, 그래프의 너비 우선 순회는 트리의 수준 순회와 유사합니다.
2.
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)

Figure 물리적 저장소 구현:

인접 행렬, 인접 연결 목록, 교차 연결 목록, 인접 다중 목록

방향 그래프 저장 방식: 교차 연결 리스트

무방향 그래프 저장 최적화: 인접 다중 리스트

그래프 순회:

1 그래프의 특정 정점부터 시작하여 그래프의 나머지 정점을 방문하고, 각 정점만 방문하도록 합니다. 한 번

2. 방문한 정점을 표시하고, 방문된 배열을 설정하고, 방문 후에는 1로 설정해야 합니다.

3, 순회 순서: 깊이 우선 순회 및 너비 우선 순회

깊이 우선 순회 DFS :

1. 미로 속을 걷는 오른손 법칙과 유사하게 한 걸음을 표시하고 반복될 때까지 오른쪽으로 계속 이동한 다음 이전 정점으로 돌아갑니다.

2 특정 정점 v에서 시작하여 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 중국어 웹사이트의 기타 관련 기사를 참조하세요!