用 PHP 实现图论算法的完整教程

// PHP 代码示例

function BFS($graph, $start) {
  $visited = [];  // 已访问的顶点
  $queue = [$start];  // 队列，用于广度优先遍历
  
  while (!empty($queue)) {
    $current = array_shift($queue);  // 从队列中取出当前访问的顶点
    if (isset($visited[$current])) {
      continue; // 如果当前顶点已访问，则跳过
    }
    
    $visited[$current] = true;  // 标记顶点已访问
    echo $current . "\n";  // 输出当前顶点

    // 将当前顶点的邻接顶点添加到队列中
    foreach ($graph[$current] as $neighbor) {
      if (!isset($visited[$neighbor])) {
        $queue[] = $neighbor;
      }
    }
  }
}

// PHP 代码示例

function DFS($graph, $start) {
  $visited = [];  // 已访问的顶点
  $stack = [$start];  // 栈，用于深度优先遍历
  
  while (!empty($stack)) {
    $current = array_pop($stack);  // 从栈中取出当前访问的顶点
    if (isset($visited[$current])) {
      continue; // 如果当前顶点已访问，则跳过
    }
    
    $visited[$current] = true;  // 标记顶点已访问
    echo $current . "\n";  // 输出当前顶点

    // 将当前顶点的邻接顶点添加到栈中
    foreach ($graph[$current] as $neighbor) {
      if (!isset($visited[$neighbor])) {
        $stack[] = $neighbor;
      }
    }
  }
}

// PHP 代码示例

function Dijkstra($graph, $start) {
  $distances = [];  // 顶点到源顶点的距离
  $visited = [];  // 已访问的顶点
  
  // 初始化
  foreach ($graph as $vertex => $edges) {
    $distances[$vertex] = ($vertex === $start) ? 0 : INF;
  }
  
  while (!empty($visited)) {
    $current = min($distances, $visited);  // 查找距离源顶点最近的未访问顶点
    $visited[$current] = true;  // 标记顶点已访问
    
    foreach ($graph[$current] as $neighbor => $weight) {
      $new_distance = $distances[$current] + $weight;
      if ($new_distance < $distances[$neighbor]) {
        $distances[$neighbor] = $new_distance;
      }
    }
  }

  return $distances;  // 返回顶点到源顶点的最短路径
}