PHP 데이터 구조-그래프 순회: 깊이 우선 및 너비 우선

그래프 순회: 깊이 우선 및 너비 우선

이전 기사 "PHP 데이터 구조 - 그래프 저장 구조"에서 그래프의 관련 저장 구조, 즉 인접 행렬과 인접 목록을 배웠습니다. 이들은 각각 순차 스토리지와 체인 스토리지의 가장 일반적인 두 가지 유형을 나타냅니다. 이제 데이터 구조가 있으므로 다음 단계는 알고리즘 부분인 이러한 데이터 구조를 작동하는 방법을 배우는 것입니다. 그래프든 트리든 순회는 매우 중요한 부분입니다. 오늘은 가장 기본적인 그래프 순회 방법 두 가지를 먼저 배워보겠습니다.

트리 순회는 그래프 순회로 진화했습니다

나무 연구에서 선순서, 순차순서, 후순서 및 수준순서 순회 형식에 대해 이야기했던 것을 아직도 기억하시나요? 실제로 pre-order, mid-order, post-order는 모두 스택 구조를 사용하여 순회하는 방식으로 먼저 흑색 경로로 갔다가 순회되지 않은 경로로 돌아오는 것이 특징입니다. 길. 레이어 순서 탐색은 큐를 사용하여 레이어별로 탐색하는 방식으로, 자식 노드를 먼저 탐색한 후 각 자식 노드의 다음 레벨 노드를 하나씩 탐색하는 것이 특징입니다.

트리 순회 방법을 검토한 후에는 그래프 순회 방법을 배우는 것이 매우 간단할 것입니다. 그래프 순회에서 가장 기본적인 두 가지 순회 형태는 스택과 큐를 기반으로 하기 때문입니다. 단지 이름이 약간 다를 뿐입니다. 스택 기반 순회 방법을 깊이 우선 순회라고 하고, 큐 기반 순회 방법을 너비 우선 순회라고 합니다. 실제로 트리에서의 첫 번째, 중간, 마지막 순서 순회와 레이어 순서 순회에 해당합니다. 본질적으로 큰 차이는 없습니다.

[추천: PHP 비디오 튜토리얼]

깊이 우선 탐색

그림에서 깊이 우선 탐색의 형태인 스택 탐색 방법으로 시작합니다. 스택의 경우 다른 하위 노드가 없는 것으로 확인될 때까지 새 노드가 스택에 계속 푸시되고, 노드에 다른 노드가 있는 것으로 확인되면 하위 노드가 스택으로 푸시됩니다. 스택. 이것이 심층 순회 아이디어입니다.

여기서는 방문한 노드를 기록해야 한다는 점에 유의해야 합니다. 특정 노드에 연결된 경로가 있는 노드가 여러 개 있는 경우 이 노드는 한 번만 방문했는지 확인하세요. 이것이 트리 구조와의 가장 큰 차이점이다. 트리가 맨 아래로 내려가고, 수평 노드 사이의 연결이 없으며, 노드에는 상위 노드가 하나만 있기 때문이다. 그래프에서 모든 노드는 다른 노드와 관련될 수 있습니다.

Adjacency Matrix

먼저 인접 행렬에 대한 깊이 우선 순회 알고리즘의 구현을 살펴보겠습니다. 지금 이해가 안 되더라도 상관없습니다. 아래로 스크롤하여 그림을 보고 함께 읽어보세요. 물론 더 나은 해결책은 직접 실행하는 것입니다.

$visited = []; // 已访问结点
function DFS_AM($graphArr, $x)
{
    global $visited;
    echo "节点：{$x}", PHP_EOL;
    $visited[$x] = true; // 当前结点标记为已访问
     
    // y 就是邻接矩阵中的横行
    for ($y = 1; $y <= count($graphArr); $y++) {
        // 循环判断第 [x][y] 个数据是否为 1，也就是是否有边
        // 并且这个结点没有被访问过
        if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
            // 进行栈递归，传递的参数是当前这个结点
            DFS_AM($graphArr, $y);
        }
    }
}
BuildGraph($graphArr); // 建立邻接矩阵图
echo &#39;请输入开始遍历的结点（1-结点数）：&#39;; 
fscanf(STDIN, "%d", $startNode); // 输入从第几个结点开始访问
DFS_AM($graphArr, $startNode); // 开始深度优先遍历

코드의 양은 많지 않습니다. 이전 글에서 인접행렬을 설정하는 코드를 사용했습니다. 잊어버리셨다면 돌아가서 보시거나 맨 아래 링크에서 소스코드를 직접 읽어보세요. 기사.

다음으로 테스트할 내용은 다음과 같습니다.

# php 5.3图的遍历：深度优先与广度优先.php
输入结点数：4
请输入边数：3
请输入边，格式为 出 入 权：1 2 1
请输入边，格式为 出 入 权：1 3 1
请输入边，格式为 出 入 权：3 4 1
请输入开始遍历的结点（1-结点数）：3
节点：3
节点：1
节点：2
节点：4

Adjacency list

물론 중간의 루프 알고리즘이 체인 특성 방법을 사용한다는 점만 제외하면 인접 목록을 순회하는 아이디어는 동일합니다.

$visited = [];  // 已访问结点
function DFS_AL($graph, $x){
    global $visited;
    $p = $graph->adjList[$x]; // 指定结点的第一个边结点
    echo "节点：{$x}", PHP_EOL; // 输出指定结点的信息
    $visited[$x] = true; // 设置该结点已被访问
    while($p != null){
        $y = $p->adjVex; // 获得边结点信息
        if(!$visited[$y]){ // 如果结点没有被访问过
            DFS_AL($graph, $y); // 进入这个边结点的深度遍历过程
        }
        $p = $p->nextArc; // 移动到下一个边结点
    }
}
$graph = BuildLinkGraph();
$graphBFS = $graph;
echo '请输入开始遍历的结点（1-结点数）：';
fscanf(STDIN, "%d", $startNode); // 输入从第几个结点开始访问
DFS_AL($graph, $startNode);// 开始深度优先遍历

그것도 매우 간단합니까? 다음으로 간단하게 테스트해 보겠습니다.

# php 5.3图的遍历：深度优先与广度优先.php
请输入 结点数 边数：
4 3
请输入边，格式为 出 入 权：1 2 1
请输入边，格式为 出 入 权：1 3 1
请输入边，格式为 出 入 权：3 4 1
请输入开始遍历的结点（1-结点数）：3
节点：3
节点：4
节点：1
节点：2

왜 출력 순서가 인접 행렬의 순서와 다른가요? 이전 기사에서 구현한 인접 목록은 헤드 보간을 사용합니다. 이후 입력 데이터는 첫 번째 입력에 3 4 1을 넣으면 인접 행렬과 동일합니다. 순회 결과는 동일합니다.

깊이우선 순회 아이콘

직접 올라와서 코드를 보고, 알고리즘에 대해 오랫동안 이야기를 나누셨는데 아직도 헷갈리시나요? 상관없습니다. 그림을 직접 살펴보겠습니다.

왼쪽은 인접 행렬이고 오른쪽은 인접 목록입니다. 우리가 테스트한 그래프는 4개의 노드와 3개의 간선으로 비교적 간단합니다. 다음은 6개의 노드와 5개의 간선으로 구성된 좀 더 복잡한 그래프입니다. 직접 테스트해 볼 수 있습니다. 각 단계의 순회 및 실행 순서는 작은 검은색 원 안의 숫자를 참조하세요. 인접 행렬의 첫 번째 그림을 사용하여 액세스 단계를 간략하게 설명하겠습니다.

• 먼저 노드 3에서 액세스를 입력한 다음 깊이 순회를 시작합니다. 이때 출력 노드 3

• 은 먼저 단계 노드 3의 루프에서 노드 1과 에지가 있다는 것을 얻었으므로 노드 1을 재귀적으로 전달하고 노드 1은 스택

• 출력 노드 1로 푸시됩니다. 현재 재귀에서 노드 1이 스택의 맨 위에 있습니다

• 在 结点1 的循环中发现 结点1 和 结点 2 有边，于是递归传入 结点2 ，结点2 入栈

• 输出 结点2，目前的递归中 结点2 在栈顶

• 注意了，重点在这里，结点2 的循环中没有发现与其它未访问的结点有边存在了，于是递归开始返回，也就是开始出栈了，依次返回到 结点1 、结点3，没有任何输出，栈空了，递归回到最外层的函数了

• 继续 结点3 的循环，发现与 结点4 有边，递归传入 结点4

• 输出 结点4，目前的递归中 结点4 在栈顶

• 结点4 的循环中没有发现其它未访问的结点及边了，递归返回，结点4 出栈

• 结点3 循环完成，遍历结束

一步一步的很清晰吧，大家试着自己分析一下下面那个复杂一些图的深度遍历顺序，看看和我们程序输出的结果是不是一样的。在很多的考研或者数据结构考试中，经常会有选择题或应用题让你手动地来写出深度优先遍历的顺序哦！

广度优先遍历

接下来就是广度优先遍历了，其实说白了就是我们在学习树的遍历时候的层序遍历。前面我们说过，深度遍历是一条路走到黑，没路了退回来。而广度遍历则是一层一层的查看，直到找到出口。

邻接矩阵

使用邻接矩阵来进行广度优先遍历的操作，其实最核心的遍历方式和深度遍历没什么区别，都是对某一个结点进行边的查找，唯一不同的就是把递归栈换成了队列而已。

$visited = [];
function BFS_AM($graphArr, $x){
    global $visited;
    $queue = InitSqQueue(); // 初始化队列
    $graphCount = count($graphArr); // 获取矩阵结点数量
    $visited[$x] = true; // 结点标记为已访问
    EnSqQueue($queue, $x); // 结点入队
    while($x){ // 循环判断结点是否 fasle
        // 遍历所有结点是否与这个结点有边
        for ($y = 1; $y <= $graphCount; $y++) {
            // 如果有边并且未访问过
            if ($graphArr[$x][$y] != 0 && !$visited[$y]) {
                $visited[$y] = true; // 结点标记为已访问
                EnSqQueue($queue, $y); // 结点入队
            }
        }
        $x = DeSqQueue($queue); // 出队一个结点
        echo $x, PHP_EOL; // 输出结点
    }
}
echo &#39;请输入开始广度遍历的结点（1-结点数）：&#39;;
fscanf(STDIN, "%d", $startNode);
BFS_AM($graphArr, $startNode); // 开始广度遍历

代码中的注释也很清晰明了了，我们直接进行测试：

……
……
请输入开始广度遍历的结点（1-结点数）：3
3
1
4
2

邻接表

同样地，我们也提供邻接表的链式广度优先遍历的核心函数。

$visited = [];
function BFS_AL($graph, $x){
    global $visited;
    $visited[$x] = true; // 结点标记为已访问
    $queue = InitSqQueue();// 初始化队列
    EnSqQueue($queue, $x); // 结点入队
    
    // 如果一直有能出队的结点，就一直循环
    // 也就是说，如果队列空了，循环就结束
    while(($i = DeSqQueue($queue))!==false){
        echo $i, PHP_EOL; // 输出结点
        $p = $graph->adjList[$i]; // 结点的第一个边结点
        while($p != null){ // 如果不为空
            $y = $p->adjVex; // 边结点信息
            if(!$visited[$y]){ // 如果没有访问过
                $visited[$y] = true; // 标记结点为已访问
                EnSqQueue($queue, $y); // 入队结点
            }
            $p = $p->nextArc; // 结点指针指向下一个
        }
    }
}
echo '请输入开始遍历的结点（1-结点数）：';
fscanf(STDIN, "%d", $startNode);
BFS_AL($graph, $startNode); // 开始广度遍历

核心的循环中的操作其实也和深度遍历没什么太大的区别，同样是换成了队列这种存储形式而已。

……
……
请输入开始广度遍历的结点（1-结点数）：3
3
4
1
2

广度优先遍历图示

好吧，上面又罗列完了算法，接下来就是图示的时间了，相信还是一看图大家就马上能明白广度优先遍历的具体步骤了。

和上面的图一样，同样还是左边是邻接矩阵，右边是邻接表。在这里，我们依然还是直接分步骤来看一下左边最上面图的遍历操作顺序：

• 输入 结点3 开始广度遍历，结点标记为已访问，这时 结点3 入队

• 使用 while 循环判断 结点x 是否为 null ，如果不为 null 进入循环体

• 遍历所有结点是否与这个结点有边，如果有边，并且这个结点没有被访问过，标记已访问，加入队列

• 出队一个元素，并赋值给 x

• 输出 x 结点的信息

广度优先遍历没有栈的回溯，就是一条线性的队列走完就完了，所以图示会非常清晰。单独一个结点我们会将和它相关的所有结点入队，然后出队最顶上的结点，这样就能够像树的层序遍历一样按照一层一层的顺序来遍历整个图。同样地，拿起纸笔，找复杂一点的图，试试能不能手写出类似于广度优先遍历顺序的题目吧！

总结

大家学完了之后是不是发现今天介绍的深度优先和广度优先两种遍历方式真的和树的遍历方式没什么太大的区别。最大的不同就是我们要标记已访问过的结点而已。不管怎么说，使用栈和队列来对树或图进行遍历是所有树和图的操作算法中最最基础的部分，也是考试和面试中最常见的问题，大家一定要深入理解掌握哦！

测试代码：
https://github.com/zhangyue0503/Data-structure-and-algorithm/blob/master/5.图/source/5.3图的遍历：深度优先与广度优先.php

위 내용은 PHP 데이터 구조-그래프 순회: 깊이 우선 및 너비 우선의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!