Skip to main content

Construct adjacency list by using adjacency matrix in php

Php program for Construct adjacency list by using adjacency matrix. Here more information.

<?php
/*
    Php program for
    Construct adjacency list using adjacency matrix
*/
class Graph
{
	public $vertices;
	public $adgeList;
	public	function __construct($matrix)
	{
		// Set number of nodes
		$this->vertices = count($matrix);
		$this->adgeList = array();
		// Create memory of adgeList of each vertice
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			array_push($this->adgeList, array());
		}
		$this->makeAdjacencyList($matrix);
	}
	// Convert into adjacency list
	public	function makeAdjacencyList($matrix)
	{
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			for ($j = 0; $j < $this->vertices; ++$j)
			{
				if ($matrix[$i][$j] == 1)
				{
					$this->addEdge($i, $j);
				}
			}
		}
	}
	public	function addEdge($u, $v)
	{
		if ($u < 0 || $u >= $this->vertices || 
            $v < 0 || $v >= $this->vertices)
		{
			return;
		}
		// Add node edge
		array_push($this->adgeList[$u], $v);
	}
	// Display graph nodes and edges
	public	function printGraph()
	{
		echo "\n Graph Adjacency List ";
		for ($i = 0; $i < $this->vertices; ++$i)
		{
			echo " \n [",$i,"] :";
			// iterate edges of i node
			for ($j = 0; $j < count($this->adgeList[$i]); $j++)
			{
				if ($j != 0)
				{
					echo " → ";
				}
				echo " ",$this->adgeList[$i][$j];
			}
		}
	}
	public static
	function main($args)
	{
		$matrix = array(
          array(0, 1, 1, 0, 1), 
          array(1, 0, 1, 0, 1), 
          array(1, 1, 0, 1, 0), 
          array(0, 1, 0, 0, 1), 
          array(1, 1, 0, 1, 0)
        );
		$g = new Graph($matrix);
		// Display graph element
		$g->printGraph();
	}
}
Graph::main(array());

Output

 Graph Adjacency List
 [0] : 1 →  2 →  4
 [1] : 0 →  2 →  4
 [2] : 0 →  1 →  3
 [3] : 1 →  4
 [4] : 0 →  1 →  3




Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment