- 浏览: 137184 次
- 性别:
- 来自: 北京
文章分类
最新评论
PHP实现图的邻接矩阵及普里姆(prim算法),弗洛伊德(floyd),迪杰斯特拉(dijkstra)算法
- 博客分类:
- 数据结构算法
<?php require 'mGraph.php'; $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->prim()); ?>
mGraph.php
<?php /** * PHP 实现图邻接矩阵 * * @author zhaojiangwei * @since 2011/10/31 17:23 */ 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); } } ?>
发表评论
文章已被作者锁定,不允许评论。
-
c实现bitmap
2013-05-14 14:34 1348直接上代码. #include <stdio.h> ... -
nginx hash源码分析
2013-02-05 19:05 1229HASH是NGINX核心数据结构之一.见几个链接.分析的很详细 ... -
贪心算法与动态规划的区别
2012-11-24 21:07 31981.贪心算法和动态规划区别 贪心算法是自顶向下的,它会先做在 ... -
PHP实现各种排序
2011-11-23 17:32 936<?php /** * 各种排序 * @aut ... -
PHP实现平衡二叉树(AVL树)
2011-11-20 17:20 2935<?php require 'bstOrder ... -
PHP实现克鲁斯卡尔(kruscal)算法
2011-11-05 21:18 1185<?php require 'edge.php ... -
php实现图的邻接表,关键路径,拓朴排序
2011-11-02 18:30 1829<?php //调用 require ... -
PHP实现二叉树,线索二叉树
2011-10-26 19:56 6464<?php require 'biTree ... -
php 实现KMP算法
2011-10-23 12:32 1847<?php /** * KMP算法的P ... -
php实现单链表(静态链表)
2011-10-21 14:40 1818<?php /* * 单链表的PH ...
相关推荐
本文将深入探讨图的邻接矩阵表示以及其中涉及的三种核心算法:迪杰斯特拉算法、普里姆算法和克鲁斯卡尔算法,并提供C++实现。 1. **图的邻接矩阵表示**: 邻接矩阵是一种二维数组,用于存储图中顶点之间的连接信息...
根据提供的文件内容,本文将详细解释两种经典的最短路径算法:迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd)算法,并通过具体的示例代码来展示这两种算法的应用场景及其工作原理。 ### 迪杰斯特拉(Dijkstra)...
接下来,书中可能会深入讨论关键的图算法,例如迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd-Warshall)算法,用于求解单源最短路径问题;普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法,用于找出图的最小生成树...
图算法中还有一些重要的算法,例如最短路径算法,如迪杰斯特拉算法(Dijkstra's algorithm)、贝尔曼-福特算法(Bellman-Ford algorithm)以及弗洛伊德算法(Floyd-Warshall algorithm)。这些算法能够帮助我们找到...
1. **迪杰斯特拉算法(Dijkstra's Algorithm)**:从源顶点开始,通过逐步扩展最短路径,更新所有顶点的最短路径。它利用优先队列(如二叉堆)来存储待处理的顶点,并保证每次取出的都是当前未处理顶点中最短路径的...
2. 最短路径算法:用于计算图中两个节点间的最短路径,其中最著名的是迪杰斯特拉(Dijkstra)算法和弗洛伊德(Floyd-Warshall)算法。 3. 最小生成树算法:用于在无向连通图中找到一棵包含所有顶点的树,这棵树的边...
- 最短路径算法:学习诸如迪杰斯特拉(Dijkstra)算法、贝尔曼-福特(Bellman-Ford)算法、弗洛伊德(Floyd)算法等计算图中路径的算法。 - 最小生成树算法:了解普里姆(Prim)算法和克鲁斯卡尔(Kruskal)算法。...
11. **Dijkstra算法**:迪杰斯特拉算法是最著名的求解单源最短路径的算法,特别适合于边的权重为非负的情况。它使用优先队列(通常用堆实现)来选取当前距离源点最近的顶点。 12. **拓扑排序**:拓扑排序是对有向无...
不过,可以预期代码会涉及图的表示(如邻接矩阵或邻接表)、排序算法(如快速排序或归并排序)以及判断环路的条件检查等核心部分。对于学习和理解最小生成树,你可以通过阅读和分析代码来加深对这些算法的理解。
4. **Dijkstra's Algorithm**(迪杰斯特拉算法):用于寻找图中从源点到所有其他顶点的最短路径。它通常结合堆或优先队列来实现,每次处理当前最短距离的顶点。 5. **Floyd-Warshall Algorithm**(弗洛伊德-沃瑟曼...
图算法还包括迪杰斯特拉算法(Dijkstra's Algorithm)用于找到单源最短路径,弗洛伊德算法(Floyd-Warshall Algorithm)用于求解所有顶点对之间的最短路径,以及克鲁斯卡尔(Kruskal's Algorithm)和普里姆(Prim's ...
3. **迪杰斯特拉算法(Dijkstra's Algorithm)**:这是一种单源最短路径算法,适用于加权有向图。它通过逐步扩展最短路径树来找到从源节点到所有其他节点的最短路径。 4. **弗洛伊德-沃普斯算法(Floyd-Warshall ...
8. **最短路径问题**:迪杰斯特拉算法(Dijkstra's algorithm)用于求解单源最短路径,要求边权非负;Floyd-Warshall算法可以处理有负权边但不允许负权环的情况。 9. **关键路径**:在有向无环图(AOE网)中,关键...
常见的图算法有深度优先搜索(DFS)、广度优先搜索(BFS)、迪杰斯特拉(Dijkstra)最短路径算法、弗洛伊德(Floyd-Warshall)所有对最短路径算法、普里姆(Prim)最小生成树算法、克鲁斯卡尔(Kruskal)最小生成树算法等。...
5. **最短路径算法**:迪杰斯特拉(Dijkstra)、弗洛伊德(Floyd-Warshall)和贝尔曼-福特(Bellman-Ford)算法,这些都是求解单源最短路径问题的重要方法,课件会详细解析它们的实现和适用条件。 6. **最小生成树*...
- 求解最短路径的迪杰斯特拉算法、最小生成树的普里姆算法和克鲁斯卡尔算法等,需要具体题目数据才能进行详细步骤分析。 这些知识点是图论的基础,对于理解和解决复杂网络问题至关重要,不仅在理论研究中重要,也...
- 迪杰斯特拉算法(Dijkstra's Algorithm):求单源最短路径,使用贪心策略,每次选取当前未访问顶点中最短路径可达的顶点。 - 弗洛伊德算法(Floyd-Warshall Algorithm):求每对顶点间的最短路径,通过动态规划...
- **迪杰斯特拉算法(Dijkstra's Algorithm)**:用于计算带权重的有向图中源节点到其他所有节点的最短路径。 - **贝尔曼-福特算法(Bellman-Ford Algorithm)**:不仅可以处理非负权重的图,还能检测负权环。 - ...