daily pastebin goal
50%
SHARE
TWEET

Untitled

a guest Feb 13th, 2018 72 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. <?php
  2.  
  3. class Graph
  4. {
  5.     protected $_len = 0;
  6.     protected $_i = 0;
  7.     protected $_g = array();
  8.     protected $_visited = array();
  9.  
  10.     public function __construct()
  11.     {
  12.         // $this->_g = array(
  13.         //     array(0, 1, 1, 0, 0, 0),
  14.         //     array(1, 0, 0, 1, 0, 0),
  15.         //     array(1, 0, 0, 1, 1, 1),
  16.         //     array(0, 1, 1, 0, 1, 0),
  17.         //     array(0, 0, 1, 1, 0, 1),
  18.         //     array(0, 0, 1, 0, 1, 0),
  19.         // );
  20.  
  21.         $this->_g = array(
  22.           'A' => array('B', 'F'),
  23.           'B' => array('A', 'D', 'E'),
  24.           'C' => array('F'),
  25.           'D' => array('B', 'E'),
  26.           'E' => array('B', 'D', 'F'),
  27.           'F' => array('A', 'C', 'E'),
  28.         );
  29.  
  30.         $this->_len = count($this->_g);
  31.  
  32.         $this->_initVisited();
  33.  
  34.         // print_r($this->_visited);exit;
  35.     }
  36.  
  37.     protected function _initVisited()
  38.     {
  39.         // for ($i = 0; $i < $this->_len; $i++) {
  40.         //     $this->_visited[$i] = 0;
  41.         // }
  42.  
  43.         foreach ($this->_g as $key => $value) {
  44.             $this->_visited[$key] = 0;  
  45.         }
  46.     }
  47.  
  48.     public function depthFirst($ori, $desti)
  49.     {
  50.         $this->_i++;
  51.         $this->_visited[$ori] = 1;
  52.        
  53.         foreach($this->_g[$ori] as $val){
  54.             if($val==$desti){
  55.                 echo $val;
  56.                 exit;
  57.             }else{
  58.                 if($this->_visited[$val] == 0){
  59.                     echo $val . "->";
  60.                     $this->depthFirst($val, $desti);
  61.                 }
  62.             }
  63.         }
  64.  
  65.         // echo $ori . "\n";
  66.  
  67.         // for ($i = 0; $i < $this->_len; $i++) {
  68.         //     if ($this->_g[$vertex][$i] == 1 && !$this->_visited[$i]) {
  69.         //         $this->depthFirst($i);
  70.         //     }
  71.         // }
  72.  
  73.         // foreach ($this->_g[] as $key => $value) {
  74.         //     if($this->_g[$ori][$key] == ){
  75.  
  76.         //     }
  77.         // }
  78.     }
  79. }
  80.  
  81. $g = new Graph();
  82. // 2 0 1 3 4 5
  83. $g->depthFirst('D', 'C');
  84. // echo $this->_i;
RAW Paste Data
Top