Mastering Graph Algorithms in PHP: Implementing Traversals and Shortest Path Algorithms

Graphs are one of the most powerful and flexible data structures in computer science, widely used for solving problems like shortest path finding, network analysis, and much more. In PHP 8, developers can leverage modern language features and optimized approaches to implement and optimize graph-related algorithms.

In this article, we will explore graph data structures, common graph traversals, and two important shortest path algorithms: Dijkstra’s and Bellman-Ford.

Understanding Graph Data Structures

A graph is a collection of nodes (vertices) connected by edges. There are two main types of graphs:

• Directed Graph: In a directed graph, the edges have a direction, meaning they go from one vertex to another.
• Undirected Graph: In an undirected graph, edges don’t have a direction; they simply connect two vertices.

We can represent graphs using two common methods in programming:

1. Adjacency Matrix: A 2D array where each cell represents an edge between two vertices.
2. Adjacency List: An array of lists (or hash maps) where each vertex has a list of connected vertices.

In this article, we will use an adjacency list to represent graphs because it's more efficient in terms of space for sparse graphs.

Example: Graph Representation

class Graph {

    private array $adjList = [];

    // Add a vertex to the graph

    public function addVertex(string $vertex): void {

        $this->adjList[$vertex] = [];

    }

    // Add an edge between two vertices

    public function addEdge(string $vertex1, string $vertex2): void {

        $this->adjList[$vertex1][] = $vertex2;

        $this->adjList[$vertex2][] = $vertex1; // For undirected graph

    }

    // Get adjacent vertices of a given vertex

    public function getAdjacencyList(string $vertex): array {

        return $this->adjList[$vertex] ?? [];

    }

}

Implementing Graph Traversals

Graph traversals allow you to visit every vertex in the graph in a systematic manner. There are two main traversal algorithms:

1. Depth-First Search (DFS)

DFS explores as far as possible along a branch before backtracking. It is often implemented using recursion or a stack.

class Graph {

    // ... (Previous methods)

    // DFS traversal

    public function depthFirstSearch(string $start): array {

        $visited = [];

        $result = [];

        $this->dfsHelper($start, $visited, $result);

        return $result;

    }

    private function dfsHelper(string $vertex, array &$visited, array &$result): void {

        if (isset($visited[$vertex])) return;

        $visited[$vertex] = true;

        $result[] = $vertex;

        foreach ($this->getAdjacencyList($vertex) as $neighbor) {

            $this->dfsHelper($neighbor, $visited, $result);

        }

    }

}

2. Breadth-First Search (BFS)

BFS explores all neighboring nodes at the present depth before moving on to nodes at the next depth level. It is implemented using a queue.

class Graph {

    // ... (Previous methods)

    // BFS traversal

    public function breadthFirstSearch(string $start): array {

        $visited = [];

        $queue = [$start];

        $result = [];

        while ($queue) {

            $vertex = array_shift($queue);

            if (isset($visited[$vertex])) continue;

            $visited[$vertex] = true;

            $result[] = $vertex;

            foreach ($this->getAdjacencyList($vertex) as $neighbor) {

                if (!isset($visited[$neighbor])) {

                    $queue[] = $neighbor;

                }

            }

        }

        return $result;

    }

}

Both DFS and BFS help in exploring the graph’s vertices in different ways, which is useful for solving problems like finding connected components, solving puzzles, etc.

Shortest Path Algorithms

Finding the shortest path between nodes is one of the most important applications of graph algorithms. Two well-known algorithms for this task are Dijkstra’s Algorithm and Bellman-Ford Algorithm.

1. Dijkstra’s Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a graph. It works only with graphs that have non-negative weights on edges.

class Graph {

    private array $adjList = [];

    private array $weights = []; // Store edge weights

    public function addVertex(string $vertex): void {

        $this->adjList[$vertex] = [];

    }

    public function addEdge(string $vertex1, string $vertex2, int $weight): void {

        $this->adjList[$vertex1][] = $vertex2;

        $this->adjList[$vertex2][] = $vertex1;

        $this->weights["$vertex1,$vertex2"] = $weight;

        $this->weights["$vertex2,$vertex1"] = $weight; // Undirected graph

    }

    public function dijkstra(string $start): array {

        $dist = [];

        $prev = [];

        $queue = [];

        // Set initial distances to infinity

        foreach ($this->adjList as $vertex => $edges) {

            $dist[$vertex] = INF;

            $prev[$vertex] = null;

            $queue[$vertex] = INF;

        }

        $dist[$start] = 0;

        $queue[$start] = 0;

        while ($queue) {

            // Get the vertex with the smallest distance

            asort($queue);

            $minVertex = key($queue);

            unset($queue[$minVertex]);

            // Visit each neighbor

            foreach ($this->getAdjacencyList($minVertex) as $neighbor) {

                $edge = "$minVertex,$neighbor";

                $alt = $dist[$minVertex] + ($this->weights[$edge] ?? INF);

                if ($alt < $dist[$neighbor]) {

                    $dist[$neighbor] = $alt;

                    $prev[$neighbor] = $minVertex;

                    $queue[$neighbor] = $alt;

                }

            }

        }

        return ['distances' => $dist, 'previous' => $prev];

    }

}

2. Bellman-Ford Algorithm

The Bellman-Ford algorithm is more versatile than Dijkstra’s because it can handle graphs with negative weight edges. It runs in O(VE) time complexity and can also detect negative weight cycles.

class Graph {

    private array $adjList = [];

    private array $weights = [];

    public function addVertex(string $vertex): void {

        $this->adjList[$vertex] = [];

    }

    public function addEdge(string $vertex1, string $vertex2, int $weight): void {

        $this->adjList[$vertex1][] = $vertex2;

        $this->weights["$vertex1,$vertex2"] = $weight;

    }

    public function bellmanFord(string $start): array {

        $dist = [];

        $dist[$start] = 0;

        // Initialize distances for all other vertices

        foreach ($this->adjList as $vertex => $edges) {

            if ($vertex !== $start) {

                $dist[$vertex] = INF;

            }

        }

        // Relax edges repeatedly

        $vertices = array_keys($this->adjList);

        for ($i = 0; $i < count($vertices) - 1; $i++) {

            foreach ($this->adjList as $vertex => $edges) {

                foreach ($edges as $neighbor) {

                    $edge = "$vertex,$neighbor";

                    $alt = $dist[$vertex] + ($this->weights[$edge] ?? INF);

                    if ($alt < $dist[$neighbor]) {

                        $dist[$neighbor] = $alt;

                    }

                }

            }

        }

        // Check for negative weight cycles

        foreach ($this->adjList as $vertex => $edges) {

            foreach ($edges as $neighbor) {

                $edge = "$vertex,$neighbor";

                if ($dist[$vertex] + ($this->weights[$edge] ?? INF) < $dist[$neighbor]) {

                    throw new Exception("Graph contains negative weight cycle");

                }

            }

        }

        return $dist;

    }

}

Conclusion

Graphs are an essential part of computer science and are widely used in many fields, such as networking, routing, and data analysis. Understanding the core graph algorithms, such as traversals (DFS and BFS) and shortest path algorithms (Dijkstra's and Bellman-Ford), is critical for solving a wide range of problems.

With PHP 8’s modern features and efficient object-oriented practices, you can easily implement and optimize these algorithms for your own projects. Understanding these techniques can help you build smarter, more efficient software that deals with complex data relationships.

Thanks for reading the article, for more Science & Technology related articles read and subscribe to peoples blog articles.