Os grafos são estruturas de dados muito úteis em muitas áreas da ciência da computação, como redes sociais, roteamento de pacotes, sistemas de recomendação, entre outras. Eles são compostos por vértices (ou nós) e arestas (ou arcos) que conectam esses vértices.Neste artigo, vamos explorar como criar um algoritmo simples de grafos em PHP, usando arrays e matrizes. Vamos começar criando uma classe Graph que representará nosso grafo.
A classe Graph terá duas propriedades: um array para armazenar os vértices e uma matriz para armazenar as arestas. Cada vértice será identificado por um índice numérico único. A matriz de arestas armazenará informações sobre quais vértices estão conectados por uma aresta.
class Graph { private $vertices = array(); private $edges = array(); public function addVertex($vertex) { $this->vertices[] = $vertex; $numVertices = count($this->vertices); for ($i = 0; $i < $numVertices; $i++) { $this->edges[$i][$numVertices-1] = 0; $this->edges[$numVertices-1][$i] = 0; } } public function addEdge($vertex1, $vertex2, $weight = 1) { $index1 = array_search($vertex1, $this->vertices); $index2 = array_search($vertex2, $this->vertices); $this->edges[$index1][$index2] = $weight; $this->edges[$index2][$index1] = $weight; } public function printGraph() { $numVertices = count($this->vertices); echo "Vertices: "; for ($i = 0; $i < $numVertices; $i++) { echo $this->vertices[$i] . " "; } echo "\nEdges:\n"; for ($i = 0; $i < $numVertices; $i++) { for ($j = 0; $j < $numVertices; $j++) { echo $this->edges[$i][$j] . " "; } echo "\n"; } }}
A função addVertex adiciona um vértice ao grafo. Ela adiciona o vértice ao array de vértices e atualiza a matriz de arestas para incluir a nova linha e coluna correspondentes ao novo vértice.A função addEdge adiciona uma aresta entre dois vértices existentes. Ela usa a função array_search para encontrar os índices numéricos correspondentes aos vértices.A função printGraph imprime uma representação do grafo na tela, exibindo primeiro os vértices e depois a matriz de arestas.
Aqui está um exemplo de como usar esta classe para criar e imprimir um grafo com três vértices e duas arestas:
$graph = new Graph();$graph->addVertex("A");$graph->addVertex("B");$graph->addVertex("C");$graph->addEdge("A", "B");$graph->addEdge("B", "C");$graph->printGraph();
Este código deve produzir a seguinte saída:
Vertices: A B C
Edges:
0 1 0
1 0 1
0 1 0 Observe que a matriz de arestas é simétrica em relação à diagonal principal, porque uma aresta entre dois vértices é bidirecional.Agora que temos um algoritmo simples de grafos em PHP, podemos usá-lo para implementar algoritmos mais complexos, como busca em profundidade, busca em largura, algoritmo de Dijkstra para caminho mínimo, entre outros.Por exemplo, aqui está um exemplo de como usar o algoritmo de busca em largura para encontrar todos os vértices alcançáveis a partir de um vértice inicial:
function BFS($graph, $startVertex) { $visited = array_fill(0, count($graph->vertices), false); $queue = array(); $visited[array_search($startVertex, $graph->vertices)] = true; array_push($queue, $startVertex); while (!empty($queue)) { $vertex = array_shift($queue); echo $vertex . " "; $index = array_search($vertex, $graph->vertices); $numVertices = count($graph->vertices); for ($i = 0; $i < $numVertices; $i++) { if ($graph->edges[$index][$i] == 1 && !$visited[$i]) { $visited[$i] = true; array_push($queue, $graph->vertices[$i]); } } }}A função BFS recebe um grafo e um vértice inicial e usa o algoritmo de busca em largura para encontrar todos os vértices alcançáveis a partir do vértice inicial. Ela usa uma matriz $visited para rastrear quais vértices já foram visitados e uma fila $queue para manter a ordem dos vértices a serem visitados.Aqui está um exemplo de como usar esta função para imprimir todos os vértices alcançáveis a partir do vértice “A” no grafo anterior:
BFS($graph, "A");Este código deve produzir a seguinte saída:
A B CIsso significa que o vértice “A” é alcançável a partir dele mesmo, bem como o vértice “B” e o vértice “C”.Conclusão:Neste artigo, exploramos como criar um algoritmo simples de grafos em PHP, usando arrays e matrizes. Também mostramos um exemplo de como usar esse algoritmo para implementar a busca em largura. Os grafos são uma ferramenta poderosa e útil na ciência da computação e podem ser usados em muitas aplicações diferentes. Espero que este artigo tenha sido útil e que você possa explorar ainda mais o mundo dos grafos com PHP.