Summary of PHP traversal algorithm-PHP Tutorial-php.cn

Home

Backend Development

PHP Tutorial

Summary of PHP traversal algorithm

Dec 20, 2017 pm 04:29 PM

php Summarize algorithm

The examples in this article describe the adjacency matrix representation of graphs implemented in PHP and several simple traversal algorithms. Share it with everyone for your reference, the details are as follows:

This time I have prepared some adjacency matrix representations of PHP implementation graphs and several simple traversal algorithms. To help everyone go further and further on the road of PHP, let’s take a look.

In web development, the application of data structures like graphs is much less than that of trees, but it often appears in some businesses. The following introduces several graph path-finding algorithms and uses PHP to implement them.

Freud's algorithm mainly traverses the vertex set according to the weight of the adjacent edges between points. If the two points are not connected, the weight will be infinite. In this way, the shortest point-to-point path can be obtained through multiple traversals. Path is the easiest to understand logically and is relatively simple to implement. The time complexity is O(n^3);

Djisktra algorithm, the classic algorithm used to implement the shortest route in OSPF, djisktra algorithm The essence is a greedy algorithm, which continuously traverses and expands the vertex path set S. Once a shorter point-to-point path is found, the original shortest path in S is replaced. After all traversals are completed, S is the shortest path set of all vertices. Dijie The time complexity of Stella's algorithm is O(n^2);

Kruskal's algorithm constructs a minimum spanning tree in the graph to connect all vertices in the graph. Thus, the shortest path is obtained. The time complexity The degree is O(N*logN);

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

&lt;?php
/**
 * PHP 实现图邻接矩阵
 */
class MGraph{
  private $vexs; //顶点数组
  private $arc; //边邻接矩阵,即二维数组
  private $arcData; //边的数组信息
  private $direct; //图的类型(无向或有向)
  private $hasList; //尝试遍历时存储遍历过的结点
  private $queue; //广度优先遍历时存储孩子结点的队列,用数组模仿
  private $infinity = 65535;//代表无穷,即两点无连接,建带权值的图时用,本示例不带权值
  private $primVexs; //prim算法时保存顶点
  private $primArc; //prim算法时保存边
  private $krus;//kruscal算法时保存边的信息
  public function MGraph($vexs, $arc, $direct = 0){
    $this-&gt;vexs = $vexs;
    $this-&gt;arcData = $arc;
    $this-&gt;direct = $direct;
    $this-&gt;initalizeArc();
    $this-&gt;createArc();
  }
  private function initalizeArc(){
    foreach($this-&gt;vexs as $value){
      foreach($this-&gt;vexs as $cValue){
        $this-&gt;arc[$value][$cValue] = ($value == $cValue ? 0 : $this-&gt;infinity);
      }
    }
  }
  //创建图 $direct:0表示无向图,1表示有向图
  private function createArc(){
    foreach($this-&gt;arcData as $key=&gt;$value){
      $strArr = str_split($key);
      $first = $strArr[0];
      $last = $strArr[1];
      $this-&gt;arc[$first][$last] = $value;
      if(!$this-&gt;direct){
        $this-&gt;arc[$last][$first] = $value;
      }
    }
  }
  //floyd算法
  public function floyd(){
    $path = array();//路径数组
    $distance = array();//距离数组
    foreach($this-&gt;arc as $key=&gt;$value){
      foreach($value as $k=&gt;$v){
        $path[$key][$k] = $k;
        $distance[$key][$k] = $v;
      }
    }
    for($j = 0; $j &lt; count($this-&gt;vexs); $j ++){
      for($i = 0; $i &lt; count($this-&gt;vexs); $i ++){
        for($k = 0; $k &lt; count($this-&gt;vexs); $k ++){
          if($distance[$this-&gt;vexs[$i]][$this-&gt;vexs[$k]] &gt; $distance[$this-&gt;vexs[$i]][$this-&gt;vexs[$j]] + $distance[$this-&gt;vexs[$j]][$this-&gt;vexs[$k]]){
            $path[$this-&gt;vexs[$i]][$this-&gt;vexs[$k]] = $path[$this-&gt;vexs[$i]][$this-&gt;vexs[$j]];
            $distance[$this-&gt;vexs[$i]][$this-&gt;vexs[$k]] = $distance[$this-&gt;vexs[$i]][$this-&gt;vexs[$j]] + $distance[$this-&gt;vexs[$j]][$this-&gt;vexs[$k]];
          }
        }
      }
    }
    return array($path, $distance);
  }
  //djikstra算法
  public function dijkstra(){
    $final = array();
    $pre = array();//要查找的结点的前一个结点数组
    $weight = array();//权值和数组
    foreach($this-&gt;arc[$this-&gt;vexs[0]] as $k=&gt;$v){
      $final[$k] = 0;
      $pre[$k] = $this-&gt;vexs[0];
      $weight[$k] = $v;
    }
    $final[$this-&gt;vexs[0]] = 1;
    for($i = 0; $i &lt; count($this-&gt;vexs); $i ++){
      $key = 0;
      $min = $this-&gt;infinity;
      for($j = 1; $j &lt; count($this-&gt;vexs); $j ++){
        $temp = $this-&gt;vexs[$j];
        if($final[$temp] != 1 &amp;&amp; $weight[$temp] &lt; $min){
          $key = $temp;
          $min = $weight[$temp];
        }
      }
      $final[$key] = 1;
      for($j = 0; $j &lt; count($this-&gt;vexs); $j ++){
        $temp = $this-&gt;vexs[$j];
        if($final[$temp] != 1 &amp;&amp; ($min + $this-&gt;arc[$key][$temp]) &lt; $weight[$temp]){
          $pre[$temp] = $key;
          $weight[$temp] = $min + $this-&gt;arc[$key][$temp];
        }
      }
    }
    return $pre;
  }
  //kruscal算法
  private function kruscal(){
    $this-&gt;krus = array();
    foreach($this-&gt;vexs as $value){
      $krus[$value] = 0;
    }
    foreach($this-&gt;arc as $key=&gt;$value){
      $begin = $this-&gt;findRoot($key);
      foreach($value as $k=&gt;$v){
        $end = $this-&gt;findRoot($k);
        if($begin != $end){
          $this-&gt;krus[$begin] = $end;
        }
      }
    }
  }
  //查找子树的尾结点
  private function findRoot($node){
    while($this-&gt;krus[$node] &gt; 0){
      $node = $this-&gt;krus[$node];
    }
    return $node;
  }
  //prim算法,生成最小生成树
  public function prim(){
    $this-&gt;primVexs = array();
    $this-&gt;primArc = array($this-&gt;vexs[0]=&gt;0);
    for($i = 1; $i &lt; count($this-&gt;vexs); $i ++){
      $this-&gt;primArc[$this-&gt;vexs[$i]] = $this-&gt;arc[$this-&gt;vexs[0]][$this-&gt;vexs[$i]];
      $this-&gt;primVexs[$this-&gt;vexs[$i]] = $this-&gt;vexs[0];
    }
    for($i = 0; $i &lt; count($this-&gt;vexs); $i ++){
      $min = $this-&gt;infinity;
      $key;
      foreach($this-&gt;vexs as $k=&gt;$v){
        if($this-&gt;primArc[$v] != 0 &amp;&amp; $this-&gt;primArc[$v] &lt; $min){
          $key = $v;
          $min = $this-&gt;primArc[$v];
        }
      }
      $this-&gt;primArc[$key] = 0;
      foreach($this-&gt;arc[$key] as $k=&gt;$v){
        if($this-&gt;primArc[$k] != 0 &amp;&amp; $v &lt; $this-&gt;primArc[$k]){
          $this-&gt;primArc[$k] = $v;
          $this-&gt;primVexs[$k] = $key;
        }
      }
    }
    return $this-&gt;primVexs;
  }
  //一般算法,生成最小生成树
  public function bst(){
    $this-&gt;primVexs = array($this-&gt;vexs[0]);
    $this-&gt;primArc = array();
    next($this-&gt;arc[key($this-&gt;arc)]);
    $key = NULL;
    $current = NULL;
    while(count($this-&gt;primVexs) &lt; count($this-&gt;vexs)){
      foreach($this-&gt;primVexs as $value){
        foreach($this-&gt;arc[$value] as $k=&gt;$v){
          if(!in_array($k, $this-&gt;primVexs) &amp;&amp; $v != 0 &amp;&amp; $v != $this-&gt;infinity){
            if($key == NULL || $v &lt; current($current)){
              $key = $k;
              $current = array($value . $k=&gt;$v);
            }
          }
        }
      }
      $this-&gt;primVexs[] = $key;
      $this-&gt;primArc[key($current)] = current($current);
      $key = NULL;
      $current = NULL;
    }
    return array(&#39;vexs&#39;=&gt;$this-&gt;primVexs, &#39;arc&#39;=&gt;$this-&gt;primArc);
  }
  //一般遍历
  public function reserve(){
    $this-&gt;hasList = array();
    foreach($this-&gt;arc as $key=&gt;$value){
      if(!in_array($key, $this-&gt;hasList)){
        $this-&gt;hasList[] = $key;
      }
      foreach($value as $k=&gt;$v){
        if($v == 1 &amp;&amp; !in_array($k, $this-&gt;hasList)){
          $this-&gt;hasList[] = $k;
        }
      }
    }
    foreach($this-&gt;vexs as $v){
      if(!in_array($v, $this-&gt;hasList))
        $this-&gt;hasList[] = $v;
    }
    return implode($this-&gt;hasList);
  }
  //广度优先遍历
  public function bfs(){
    $this-&gt;hasList = array();
    $this-&gt;queue = array();
    foreach($this-&gt;arc as $key=&gt;$value){
      if(!in_array($key, $this-&gt;hasList)){
        $this-&gt;hasList[] = $key;
        $this-&gt;queue[] = $value;
        while(!empty($this-&gt;queue)){
          $child = array_shift($this-&gt;queue);
          foreach($child as $k=&gt;$v){
            if($v == 1 &amp;&amp; !in_array($k, $this-&gt;hasList)){
              $this-&gt;hasList[] = $k;
              $this-&gt;queue[] = $this-&gt;arc[$k];
            }
          }
        }
      }
    }
    return implode($this-&gt;hasList);
  }
  //执行深度优先遍历
  public function excuteDfs($key){
    $this-&gt;hasList[] = $key;
    foreach($this-&gt;arc[$key] as $k=&gt;$v){
      if($v == 1 &amp;&amp; !in_array($k, $this-&gt;hasList))
        $this-&gt;excuteDfs($k);
    }
  }
  //深度优先遍历
  public function dfs(){
    $this-&gt;hasList = array();
    foreach($this-&gt;vexs as $key){
      if(!in_array($key, $this-&gt;hasList))
        $this-&gt;excuteDfs($key);
    }
    return implode($this-&gt;hasList);
  }
  //返回图的二维数组表示
  public function getArc(){
    return $this-&gt;arc;
  }
  //返回结点个数
  public function getVexCount(){
    return count($this-&gt;vexs);
  }
}
$a = array(&#39;a&#39;, &#39;b&#39;, &#39;c&#39;, &#39;d&#39;, &#39;e&#39;, &#39;f&#39;, &#39;g&#39;, &#39;h&#39;, &#39;i&#39;);
$b = array(&#39;ab&#39;=&gt;&#39;10&#39;, &#39;af&#39;=&gt;&#39;11&#39;, &#39;bg&#39;=&gt;&#39;16&#39;, &#39;fg&#39;=&gt;&#39;17&#39;, &#39;bc&#39;=&gt;&#39;18&#39;, &#39;bi&#39;=&gt;&#39;12&#39;, &#39;ci&#39;=&gt;&#39;8&#39;, &#39;cd&#39;=&gt;&#39;22&#39;, &#39;di&#39;=&gt;&#39;21&#39;, &#39;dg&#39;=&gt;&#39;24&#39;, &#39;gh&#39;=&gt;&#39;19&#39;, &#39;dh&#39;=&gt;&#39;16&#39;, &#39;de&#39;=&gt;&#39;20&#39;, &#39;eh&#39;=&gt;&#39;7&#39;,&#39;fe&#39;=&gt;&#39;26&#39;);//键为边,值权值
$test = new MGraph($a, $b);
print_r($test-&gt;bst());

Copy after login

Row result:

Array
(
  [vexs] =&gt; Array
    (
      [0] =&gt; a
      [1] =&gt; b
      [2] =&gt; f
      [3] =&gt; i
      [4] =&gt; c
      [5] =&gt; g
      [6] =&gt; h
      [7] =&gt; e
      [8] =&gt; d
    )
  [arc] =&gt; Array
    (
      [ab] =&gt; 10
      [af] =&gt; 11
      [bi] =&gt; 12
      [ic] =&gt; 8
      [bg] =&gt; 16
      [gh] =&gt; 19
      [he] =&gt; 7
      [hd] =&gt; 16
    )
)

Copy after login

I believe you have mastered the method after reading these cases. For more exciting information, please pay attention to other related articles on the PHP Chinese website!