How to write a depth-first search algorithm for graphs using PHP

How to write a depth-first search algorithm for a graph using PHP

Depth-first search (DFS) is a graph traversal algorithm that explores as deeply as possible along a branch in the graph until it cannot continue. until. Then backtrack to the previous node and continue exploring other branches until all nodes have been visited. In this article, we will learn how to write a depth-first search algorithm for graphs using PHP.

First, we create a node class to represent the nodes in the graph:

class Node {
   public $value;
   public $visited;
   public $neighbors;

   public function __construct($value) {
      $this->value = $value;
      $this->visited = false;
      $this->neighbors = array();
   }

   public function addNeighbor($neighbor) {
      array_push($this->neighbors, $neighbor);
   }
}

Each node has a value, a visited tag and an array of neighbors. In the constructor, we initialize these properties.

Next, we create a graph class and implement the depth-first search algorithm:

class Graph {
   public $nodes;

   public function __construct() {
      $this->nodes = array();
   }

   public function addNode($value) {
      $node = new Node($value);
      array_push($this->nodes, $node);
   }

   public function getNode($value) {
      foreach ($this->nodes as $node) {
         if ($node->value == $value) {
            return $node;
         }
      }
      return null;
   }

   public function addEdge($value1, $value2) {
      $node1 = $this->getNode($value1);
      $node2 = $this->getNode($value2);
      $node1->addNeighbor($node2);
      $node2->addNeighbor($node1);
   }

   public function depthFirstSearch($startNode) {
      $stack = new SplStack();
      $stack->push($startNode);
      $startNode->visited = true;

      while (!$stack->isEmpty()) {
         $currentNode = $stack->pop();
         echo $currentNode->value . " ";

         foreach ($currentNode->neighbors as $neighbor) {
            if (!$neighbor->visited) {
               $stack->push($neighbor);
               $neighbor->visited = true;
            }
         }
      }
   }
}

The constructor initializes an empty node array. The addNode method is used to add a new node to the graph, and the getNode method is used to obtain the node object through the node value.

The addEdge method is used to add an edge between two nodes. This edge and other edges are bidirectional. The depthFirstSearch method uses a stack to implement the depth-first search algorithm. First, the starting node is pushed onto the stack and marked as visited. Then, the current node is popped from the stack, the node's value is output, and its unvisited neighbor nodes are pushed onto the stack and marked as visited. Repeat this process until the stack is empty.

The following is a usage example:

$graph = new Graph();
$graph->addNode("A");
$graph->addNode("B");
$graph->addNode("C");
$graph->addNode("D");
$graph->addNode("E");

$graph->addEdge("A", "B");
$graph->addEdge("A", "C");
$graph->addEdge("B", "D");
$graph->addEdge("C", "E");

echo "Depth First Search: ";
$graph->depthFirstSearch($graph->getNode("A"));

The output result is: A B D C E

We created a graph and added some nodes and edges. Then, call the depthFirstSearch method to perform a depth-first search, starting from node "A".

The above is a sample code on how to use PHP to write a depth-first search algorithm for graphs. Depth-first search is a powerful graph traversal algorithm that is very useful for solving some graph-related problems.

The above is the detailed content of How to write a depth-first search algorithm for graphs using PHP. For more information, please follow other related articles on the PHP Chinese website!