PHP는 그래프 인접 행렬 표현과 순회 알고리즘을 구현합니다.
- 墨辰丷원래의
- 2018-05-17 10:23:271571검색
이 글에서는 주로 PHP 구현 그래프의 인접 행렬 표현과 몇 가지 간단한 순회 알고리즘을 소개합니다. 인접 행렬을 기반으로 한 PHP 구현 그래프의 정의와 관련 순회 연산 기술을 예제 형식으로 분석합니다.
자세한 내용은 다음과 같습니다.
웹 개발에서 그래프 데이터 구조는 트리보다 훨씬 덜 사용되지만 일부 비즈니스에서는 종종 나타나는데, 다음은 여러 그래프 경로 찾기 알고리즘이며 PHP로 구현됩니다.
Floyd 독일 알고리즘은 주로 점 사이의 인접한 가장자리의 가중치에 따라 정점을 순회합니다. 이렇게 하면 점에서 점까지의 최단 경로를 여러 번의 순회를 통해 얻을 수 있습니다. , 이는 논리적으로 가장 잘 이해되며 구현도 비교적 간단하고 시간 복잡도는 O(n^3)입니다.
Dijsktra 알고리즘은 OSPF에서 최단 경로를 구현하는 데 사용되는 고전적인 알고리즘이며 djisktra 알고리즘의 핵심은 다음과 같습니다. 정점 경로 집합 S를 지속적으로 순회하고 확장하는 그리디 알고리즘은 더 짧은 지점 간 경로가 발견되면 S의 원래 최단 경로가 모든 순회를 완료한 후 모든 정점 중 최단 경로 집합이 됩니다. Dijkstra 알고리즘의 시간 복잡도는 O(n^2)입니다.
Kruskal 알고리즘은 그래프의 모든 정점을 연결하기 위해 그래프에 최소 신장 트리를 구성합니다. 따라서 시간 복잡도는 O(N*)입니다. logN);
<?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->vexs = $vexs;
$this->arcData = $arc;
$this->direct = $direct;
$this->initalizeArc();
$this->createArc();
}
private function initalizeArc(){
foreach($this->vexs as $value){
foreach($this->vexs as $cValue){
$this->arc[$value][$cValue] = ($value == $cValue ? 0 : $this->infinity);
}
}
}
//创建图 $direct:0表示无向图,1表示有向图
private function createArc(){
foreach($this->arcData as $key=>$value){
$strArr = str_split($key);
$first = $strArr[0];
$last = $strArr[1];
$this->arc[$first][$last] = $value;
if(!$this->direct){
$this->arc[$last][$first] = $value;
}
}
}
//floyd算法
public function floyd(){
$path = array();//路径数组
$distance = array();//距离数组
foreach($this->arc as $key=>$value){
foreach($value as $k=>$v){
$path[$key][$k] = $k;
$distance[$key][$k] = $v;
}
}
for($j = 0; $j < count($this->vexs); $j ++){
for($i = 0; $i < count($this->vexs); $i ++){
for($k = 0; $k < count($this->vexs); $k ++){
if($distance[$this->vexs[$i]][$this->vexs[$k]] > $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]]){
$path[$this->vexs[$i]][$this->vexs[$k]] = $path[$this->vexs[$i]][$this->vexs[$j]];
$distance[$this->vexs[$i]][$this->vexs[$k]] = $distance[$this->vexs[$i]][$this->vexs[$j]] + $distance[$this->vexs[$j]][$this->vexs[$k]];
}
}
}
}
return array($path, $distance);
}
//djikstra算法
public function dijkstra(){
$final = array();
$pre = array();//要查找的结点的前一个结点数组
$weight = array();//权值和数组
foreach($this->arc[$this->vexs[0]] as $k=>$v){
$final[$k] = 0;
$pre[$k] = $this->vexs[0];
$weight[$k] = $v;
}
$final[$this->vexs[0]] = 1;
for($i = 0; $i < count($this->vexs); $i ++){
$key = 0;
$min = $this->infinity;
for($j = 1; $j < count($this->vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 && $weight[$temp] < $min){
$key = $temp;
$min = $weight[$temp];
}
}
$final[$key] = 1;
for($j = 0; $j < count($this->vexs); $j ++){
$temp = $this->vexs[$j];
if($final[$temp] != 1 && ($min + $this->arc[$key][$temp]) < $weight[$temp]){
$pre[$temp] = $key;
$weight[$temp] = $min + $this->arc[$key][$temp];
}
}
}
return $pre;
}
//kruscal算法
private function kruscal(){
$this->krus = array();
foreach($this->vexs as $value){
$krus[$value] = 0;
}
foreach($this->arc as $key=>$value){
$begin = $this->findRoot($key);
foreach($value as $k=>$v){
$end = $this->findRoot($k);
if($begin != $end){
$this->krus[$begin] = $end;
}
}
}
}
//查找子树的尾结点
private function findRoot($node){
while($this->krus[$node] > 0){
$node = $this->krus[$node];
}
return $node;
}
//prim算法,生成最小生成树
public function prim(){
$this->primVexs = array();
$this->primArc = array($this->vexs[0]=>0);
for($i = 1; $i < count($this->vexs); $i ++){
$this->primArc[$this->vexs[$i]] = $this->arc[$this->vexs[0]][$this->vexs[$i]];
$this->primVexs[$this->vexs[$i]] = $this->vexs[0];
}
for($i = 0; $i < count($this->vexs); $i ++){
$min = $this->infinity;
$key;
foreach($this->vexs as $k=>$v){
if($this->primArc[$v] != 0 && $this->primArc[$v] < $min){
$key = $v;
$min = $this->primArc[$v];
}
}
$this->primArc[$key] = 0;
foreach($this->arc[$key] as $k=>$v){
if($this->primArc[$k] != 0 && $v < $this->primArc[$k]){
$this->primArc[$k] = $v;
$this->primVexs[$k] = $key;
}
}
}
return $this->primVexs;
}
//一般算法,生成最小生成树
public function bst(){
$this->primVexs = array($this->vexs[0]);
$this->primArc = array();
next($this->arc[key($this->arc)]);
$key = NULL;
$current = NULL;
while(count($this->primVexs) < count($this->vexs)){
foreach($this->primVexs as $value){
foreach($this->arc[$value] as $k=>$v){
if(!in_array($k, $this->primVexs) && $v != 0 && $v != $this->infinity){
if($key == NULL || $v < current($current)){
$key = $k;
$current = array($value . $k=>$v);
}
}
}
}
$this->primVexs[] = $key;
$this->primArc[key($current)] = current($current);
$key = NULL;
$current = NULL;
}
return array('vexs'=>$this->primVexs, 'arc'=>$this->primArc);
}
//一般遍历
public function reserve(){
$this->hasList = array();
foreach($this->arc as $key=>$value){
if(!in_array($key, $this->hasList)){
$this->hasList[] = $key;
}
foreach($value as $k=>$v){
if($v == 1 && !in_array($k, $this->hasList)){
$this->hasList[] = $k;
}
}
}
foreach($this->vexs as $v){
if(!in_array($v, $this->hasList))
$this->hasList[] = $v;
}
return implode($this->hasList);
}
//广度优先遍历
public function bfs(){
$this->hasList = array();
$this->queue = array();
foreach($this->arc as $key=>$value){
if(!in_array($key, $this->hasList)){
$this->hasList[] = $key;
$this->queue[] = $value;
while(!empty($this->queue)){
$child = array_shift($this->queue);
foreach($child as $k=>$v){
if($v == 1 && !in_array($k, $this->hasList)){
$this->hasList[] = $k;
$this->queue[] = $this->arc[$k];
}
}
}
}
}
return implode($this->hasList);
}
//执行深度优先遍历
public function excuteDfs($key){
$this->hasList[] = $key;
foreach($this->arc[$key] as $k=>$v){
if($v == 1 && !in_array($k, $this->hasList))
$this->excuteDfs($k);
}
}
//深度优先遍历
public function dfs(){
$this->hasList = array();
foreach($this->vexs as $key){
if(!in_array($key, $this->hasList))
$this->excuteDfs($key);
}
return implode($this->hasList);
}
//返回图的二维数组表示
public function getArc(){
return $this->arc;
}
//返回结点个数
public function getVexCount(){
return count($this->vexs);
}
}
$a = array('a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i');
$b = array('ab'=>'10', 'af'=>'11', 'bg'=>'16', 'fg'=>'17', 'bc'=>'18', 'bi'=>'12', 'ci'=>'8', 'cd'=>'22', 'di'=>'21', 'dg'=>'24', 'gh'=>'19', 'dh'=>'16', 'de'=>'20', 'eh'=>'7','fe'=>'26');//键为边,值权值
$test = new MGraph($a, $b);
print_r($test->bst());
실행 결과:
Array
(
[vexs] => Array
(
[0] => a
[1] => b
[2] => f
[3] => i
[4] => c
[5] => g
[6] => h
[7] => e
[8] => d
)
[arc] => Array
(
[ab] => 10
[af] => 11
[bi] => 12
[ic] => 8
[bg] => 16
[gh] => 19
[he] => 7
[hd] => 16
)
)관련 권장 사항:
깊이와 너비 우선 단계에 대한 자세한 설명 PHP의 이진 트리에 대한 Versal 알고리즘
다중 트리의 재귀 순회 및 비재귀 순회 알고리즘 공유에 대한 JavaScript
위 내용은 PHP는 그래프 인접 행렬 표현과 순회 알고리즘을 구현합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!
성명：
본 글의 내용은 네티즌들의 자발적인 기여로 작성되었으며, 저작권은 원저작자에게 있습니다. 본 사이트는 이에 상응하는 법적 책임을 지지 않습니다. 표절이나 침해가 의심되는 콘텐츠를 발견한 경우 admin@php.cn으로 문의하세요.