当前位置:  首页>> 技术小册>> PHP程序员面试算法宝典

第十四章:实战四:树与图算法应用

在软件开发领域,尤其是在PHP程序员面试中,树与图算法的应用是考察应聘者算法设计与分析能力的重要环节。树与图作为数据结构中的两大类,不仅在理论研究中占据重要地位,在解决实际问题时也展现出其强大的威力。本章将深入探讨几种常见的树与图算法,并通过实战案例展示它们在PHP中的具体应用。

1. 树的基础与遍历算法

1.1 树的基本概念

树是一种非线性数据结构,由n(n≥0)个节点组成,每个节点有零个或多个子节点,没有父节点的节点称为根节点,每个非根节点有且仅有一个父节点。树中不存在环,即任意两个节点之间只有一条路径相连。

1.2 树的遍历算法

  • 前序遍历(Preorder Traversal):首先访问根节点,然后遍历左子树,最后遍历右子树。
  • 中序遍历(Inorder Traversal):首先遍历左子树,然后访问根节点,最后遍历右子树。这种遍历方式在二叉搜索树中尤为重要,因为中序遍历的结果是有序的。
  • 后序遍历(Postorder Traversal):首先遍历左子树,然后遍历右子树,最后访问根节点。
  • 层次遍历(Level Order Traversal):按从上到下、从左到右的顺序遍历树的每个节点。

PHP实现示例

  1. class TreeNode {
  2. public $val;
  3. public $left;
  4. public $right;
  5. function __construct($val = 0, $left = null, $right = null) {
  6. $this->val = $val;
  7. $this->left = $left;
  8. $this->right = $right;
  9. }
  10. }
  11. function preorderTraversal($root) {
  12. $result = [];
  13. preorderHelper($root, $result);
  14. return $result;
  15. }
  16. function preorderHelper($node, &$result) {
  17. if ($node === null) return;
  18. $result[] = $node->val;
  19. preorderHelper($node->left, $result);
  20. preorderHelper($node->right, $result);
  21. }
  22. // 类似地,可以实现中序、后序遍历和层次遍历

2. 二叉搜索树(BST)

2.1 BST的定义与性质

二叉搜索树(Binary Search Tree, BST)是一种特殊的二叉树,它满足对于树中的任意节点X,其左子树中的所有节点的值都小于X的值,其右子树中的所有节点的值都大于X的值。BST的中序遍历结果是一个递增的有序序列。

2.2 BST的操作

  • 插入:保持BST的性质,将新节点插入到合适的位置。
  • 删除:删除节点时,需考虑节点为叶子节点、仅有一个子节点或有两个子节点的情况,并维护BST的性质。
  • 查找:通过比较节点值与目标值的大小,决定是向左子树还是右子树递归查找。

PHP实现示例(仅展示插入和查找):

  1. function insertIntoBST($root, $val) {
  2. if ($root === null) {
  3. return new TreeNode($val);
  4. }
  5. if ($val < $root->val) {
  6. $root->left = insertIntoBST($root->left, $val);
  7. } else {
  8. $root->right = insertIntoBST($root->right, $val);
  9. }
  10. return $root;
  11. }
  12. function searchBST($root, $val) {
  13. if ($root === null || $root->val === $val) {
  14. return $root;
  15. }
  16. if ($val < $root->val) {
  17. return searchBST($root->left, $val);
  18. }
  19. return searchBST($root->right, $val);
  20. }

3. 图的表示与遍历算法

3.1 图的表示

图通常由顶点(Vertex)和边(Edge)组成,根据边是否有方向可分为有向图和无向图。图的表示主要有邻接矩阵和邻接表两种方式。

  • 邻接矩阵:用一个二维数组表示,adjMatrix[i][j]的值为1表示顶点i到顶点j有边,为0则无。
  • 邻接表:对每个顶点,用一个列表存储与其相连的所有顶点。

3.2 图的遍历算法

  • 深度优先搜索(DFS):通过递归或栈实现,尽可能深地遍历图的分支。
  • 广度优先搜索(BFS):通过队列实现,按层次遍历图的节点。

PHP实现示例(以邻接表表示图,并实现DFS):

  1. class Graph {
  2. private $adjList = [];
  3. function addEdge($u, $v) {
  4. $this->adjList[$u][] = $v;
  5. // 无向图需添加:$this->adjList[$v][] = $u;
  6. }
  7. function DFS($v, &$visited) {
  8. $visited[$v] = true;
  9. echo $v . " ";
  10. foreach ($this->adjList[$v] as $i) {
  11. if (!$visited[$i]) {
  12. $this->DFS($i, $visited);
  13. }
  14. }
  15. }
  16. function DFSUtil() {
  17. $visited = array_fill(0, count($this->adjList), false);
  18. foreach (array_keys($this->adjList) as $i) {
  19. if (!$visited[$i]) {
  20. $this->DFS($i, $visited);
  21. }
  22. }
  23. }
  24. }
  25. // 使用示例
  26. $g = new Graph();
  27. $g->addEdge(0, 1);
  28. $g->addEdge(0, 2);
  29. $g->addEdge(1, 2);
  30. $g->addEdge(2, 0);
  31. $g->addEdge(2, 3);
  32. $g->addEdge(3, 3);
  33. $g->DFSUtil(); // 输出遍历结果

4. 实战案例:最短路径问题

4.1 Dijkstra算法

Dijkstra算法用于解决单源最短路径问题,即在图中找到从一个顶点到其他所有顶点的最短路径。算法使用贪心策略,逐步扩展已找到最短路径的顶点集合。

PHP实现Dijkstra算法(简化版):

  1. function dijkstra($graph, $src) {
  2. $distances = array_fill(0, count($graph), PHP_INT_MAX);
  3. $distances[$src] = 0;
  4. $priorityQueue = new SplPriorityQueue();
  5. foreach (array_keys($graph) as $vertex) {
  6. $priorityQueue->insert([$distances[$vertex], $vertex], -$distances[$vertex]);
  7. }
  8. while (!$priorityQueue->isEmpty()) {
  9. [$dist, $u] = $priorityQueue->extract();
  10. if ($dist > $distances[$u]) continue;
  11. foreach ($graph[$u] as $v => $weight) {
  12. $distance = $dist + $weight;
  13. if ($distance < $distances[$v]) {
  14. $distances[$v] = $distance;
  15. $priorityQueue->insert([$distance, $v], -$distance);
  16. }
  17. }
  18. }
  19. return $distances;
  20. }
  21. // 假设图以邻接表形式给出

5. 总结

本章通过介绍树与图的基本概念、遍历算法、以及在实际问题中的应用(如BST的操作、图的遍历、最短路径问题等),展示了树与图算法的强大功能。掌握这些算法不仅有助于提升PHP程序员的算法设计能力,更能帮助他们在面对复杂问题时找到有效的解决方案。未来,随着技术的不断进步,树与图算法的应用领域还将不断拓展,为软件开发带来更多可能。