PHP数据结构(九) ——图的定义、存储与两种方式遍历

PHP数据结构(九)——图的定义、存储与两种方式遍历

(原创内容,转载请注明来源,谢谢)

一、定义和术语

1、不同于线性结构和树,图是任意两个元素之间都可以有关联的数据结构。

2、顶点:数据元素;弧:顶点A至顶点B的连线,弧是单向的,出发的点称为弧尾,抵达的点称为弧头;边:顶点A和B之间的连线,没有方向性。

3、有向图:由顶点和弧组成的图;无向图:由顶点和边组成的图。

4、完全有向图:n个顶点有n(n-1)个弧;完全无向图:n个顶点有n(n-1)/2个边。

5、稀疏图:边或弧很少的图(e<nlogn),反之为稠密图。

6、权:弧或边带有的系数;网:带权的图。

7、子图:图的边和顶点都被含于另一个图,则该图是另一个图的子图。

8、无向图的邻接点:两个顶点A、B和其连接的边x都属于某个图,则称这两个点A、B互为邻接点,连接的边x依附于这两个邻接点,A、B与x相关联。

9、有向图的邻接点:两个顶点A、B和弧x=A->B都属于某个图,则称这两个点A邻接到B,B邻接自A, A、B与x相关联。

10、无向图的度:与顶点V相关联的边的数目称为V的度,记作TD(V)。

11、有向图的度:顶点V作为弧尾的弧的数目称为出度,记作OD(V);顶点V作为弧头的弧的数目称为入度,记作ID(V)。

12、路径是指从顶点A经过若干边或弧抵达顶点B,经过的边或弧的数目称为路径的长度,起止点相同的路径称为回路或环。顶点不重复的路径称为简单路径,起止点以外不重复的路径称为简单回路或简单环。

13、无向图与连通:两个顶点之间有路径,称为两个顶点连通;任意两个顶点连通,称为整个图为连通图;无向图的极大连通子图称为连通分量。

14、有向图与强连通:每一对(v,v’)(v不等于v’)都有路径,称为强连通图。有向图的极大连通子图称为强连通分量。

15、生成树含义:生成树是连通图的极小连通子图,包含图的全部顶点,但是只有n-1条边。

16、有向树含义:有向图中,恰有一个顶点入度为0,其余顶点入度为1。

17、生成森林:若干个数,含有图的全部顶点,但是只有足以构成若干不相交的树的弧。

二、存储结构

图通常没有顺序存储结构,但是可以借助数组(通常是二维数组)进行存储。因此,图的存储结构有:数组表示法、邻接表、邻接多重表、十字链表等。

1、数组表示法

从0开始,给每个顶点一个下标,用二位数组arr[i][j](i、j属于顶点)表示顶点i和顶点j的连通情况。连通时arr[i][j]=1(如果是带权的,则连通时arr[i][j]=wij,即ij连接线的权值),不连通时arr[i][j]=0。

对于无向图,数组表示法表示的图是一个对称矩阵,可以仅存半个矩阵节约空间。

2、邻接表

邻接表采用链表结构,每条边或弧有三个存储空间,分别表示第一个节点、边的权值、下一个节点的位置。因此,对于有向图,邻接表是出度表。如果需要入度表,则称作逆邻接表。

有向图和无向图邻接表示例图如下:

3、十字链表

十字链表是针对有向图的一种存储方式,其结合了有向图的邻接表和逆邻接表,在邻接表的基础上,加一个字段,用于存储以此节点作为弧头的位置。则每个节点都可以追溯到其下一个节点,也可以找回其前一个节点。

4、邻接多重表

邻接多重表是针对无向图的一种存储方式。使用此存储方式,主要是改进无向图邻接表存储时的一个缺点——改动其中任一内容,需要同时改动对应的另一个内容,因为在无向图中边ab和ba是一样的,改动ab的内容,要同步改动ba的内容。邻接多重表,即对于一条边,仅用一个存储结构进行存储,不区分ab或者ba的方式。

三、图的遍历

1、概念

1)图的遍历,表示从图的某一个顶点出发,访问每个节点有且仅有一次。

2)为了避免重复反问,需要记录已经访问过的节点。

3)有两种方式进行遍历,深度优先搜索和广度优先搜索。

2、深度优先搜索

深度优先搜索,运用到栈的概念,当多个点和一个点成线时,先遍历一个节点,并优先遍历其子节点,直至确认没有子节点,才遍历点的下一个节点。

3、广度优先搜索

广度优先搜索,运用到队列的概念,遍历一个点时,先遍历其每一个节点,再按照第一次遍历的顺序,遍历每个节点的子节点。

4、范例

如下图所示。

PHP代码执行结果如下:

代码核心步骤:

1、根据指定的输入方式,把各节点的关系生成图。

2、深度优先算法:采用栈(后进先出LIFO)的思想,遍历节点时,被遍历的节点出栈,再遍历其子节点,将子节点逐一进栈。需要注意的是,为了防止重复遍历,被遍历过的节点以及已经进栈的节点,需要用一个数组存着,避免再次进站。

3、广度优先算法:采用队列(先进先出FIFO)的思想,遍历节点时,被遍历的节点出队列,再遍历其子节点。关键要点和深度优先算法类似。

PHP源码如下:

<?php
//实现连通图的深度、广度优先搜索
class Node{
         public$val = null;
         public$arrNext = array();//存储下一个节点位置的数组
         publicfunction __construct($val = null){
                   $this->val= $val;
         }
}
class Graph{
         //建立连通图,nodes =array('val1'=>array('val2','val3'..),'val2'=>array(...));
         //返回第一个节点,由于是连通图,可以根据第一个节点遍历整个图
         publicfunction generate(array $nodes){
                   $arrNodes= array_keys($nodes);
                   $resNodes= array();
                   foreach($arrNodesas $nodeVal){
                            $resNodes[$nodeVal]= new Node($nodeVal);
                   }
                   foreach($nodesas $key => $val){
                            foreach($valas $node){
                                     if(isset($resNodes[$node]) &&is_object($resNodes[$node])){
                                               $resNodes[$key]->arrNext[]= $resNodes[$node];
                                     }
                            }
                   }
                   returncurrent($resNodes);
         }
         //深度优先搜索
         publicfunction searchByDeep(Node $node){
                   $resultWord= array();//存放遍历结果
                   $nodeStack= array();//存放遍历过程中的中间结果
                   $wordStack= array();//**存放当前已经进栈的节点,防止重复进栈**
                   array_push($nodeStack,$node);
                   array_push($wordStack,$node->val);
                   while(!empty($nodeStack)){
                            $curNode= array_pop($nodeStack);
                            array_push($resultWord,$curNode->val);//节点进栈
                            $arrNext= $curNode->arrNext;
                            //遍历节点的next数组,找出所有的子节点
                            for($i=count($arrNext)-1;$i>=0;$i--){
                                     $curChildNode= $arrNext[$i];
                                     //判断节点不在结果集且不在栈内,则进栈,避免重复
                                     if(!in_array($curChildNode->val,$resultWord) && !in_array($curChildNode->val, $wordStack)){
                                               array_push($nodeStack,$curChildNode);
                                               array_push($wordStack,$curChildNode->val);//标记该节点已经进栈
                                     }
                            }
                   }
                   return$resultWord;
         }
         //广度优先搜索
         publicfunction searchByWide(Node $node){
             $resultWord= array();//存放遍历结果
             $nodeStack= array();//存放遍历过程中的中间结果
             $wordStack= array();//**存放已经遍历过子节点的节点,防止重复遍历**
             array_push($nodeStack,$node);
             while(!empty($nodeStack)){
                      $curNode= array_shift($nodeStack);//第一个节点出栈,实现队列
                      array_push($resultWord,$curNode->val);//节点进栈
                      array_push($wordStack,$curNode->val);//即将开始遍历其子节点
                       $arrNext= $curNode->arrNext;
                       //遍历节点的next数组,找出所有的子节点
                       for($i=0;$i<count($arrNext);$i++){
                            $curChildNode= $arrNext[$i];
                             //判断节点不在结果集且不在栈内,则进栈,避免重复
                         if(!in_array($curChildNode->val,$resultWord) && !in_array($curChildNode->val, $wordStack)){
                      array_push($nodeStack,$curChildNode);
                      array_push($wordStack,$curChildNode->val);//标记该节点已经进栈
                                     }                                   
                            }                          
                   }
                   return$resultWord;
         }
}
$graph = new Graph();
$arrNode = array(
         'a'=> array('b', 'f'),
         'b'=> array('a', 'c', 'd'),
         'c'=> array('b', 'd', 'e'),
         'd'=> array('b', 'c'),
         'e'=> array('c'),
         'f'=> array('a', 'g', 'h'),
         'g'=> array('f', 'h'),
         'h'=> array('f', 'g')
);
$graphTree = $graph->generate($arrNode);
$res = $graph->searchByDeep($graphTree);
echo '<br />深度优先搜索的结果是:';
print_r($res);
echo '<br />广度优先搜索的结果是:';
$res = $graph->searchByWide($graphTree);
print_r($res);

——written by linhxx 2017.07.08

相关阅读:

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践2)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(实践1)

PHP数据结构(八) ——赫夫曼树实现字符串编解码(理论)

PHP数据结构(七) ——串与实现KMP算法

PHP数据结构(六) ——树与二叉树之概念及存储结构

PHP数据结构(六) ——数组的相乘、广义表

PHP数据结构(五) ——数组的压缩与转置

PHP数据结构(四) ——队列

PHP数据结构(三)——运用栈实现括号匹配

PHP数据结构(二)——链式结构线性表

PHP数据结构(一)——顺序结构线性表

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-07-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏有趣的Python

数据结构探险之图篇(上)理论篇数据结构探险之图篇

数据结构探险之图篇 什么是图? 如下图:无向图 & 有向图 箭头分方向。 无向图中每条认为有来有回两条线 ? 无向图&有向图 图中的概念: ? 有向图...

3636
来自专栏开发与安全

算法:图的深度优先遍历(Depth First Search)

图的遍历和树的遍历类似,我们希望从图中某一顶点出发访遍图中其余顶点,且使每一个顶点仅被访问一次,这一过程就叫做图的遍历(Traverse Graph)。 图的遍...

2686
来自专栏Android机动车

数据结构——图相关概念

可是现实生活中,好多关系不再是一对一或一对多,比如人和人之间的关系,会互相认识,就要考虑多对多的情况。这就是今天要介绍的——图。

772
来自专栏章鱼的慢慢技术路

浅谈图的广度优先遍历

1084
来自专栏人工智能LeadAI

Python数据分析模块 | pandas做数据分析(三):统计相关函数

计算操作 1、pandas.series.value_counts Series.value_counts(normalize=False,sort=True,...

3388
来自专栏小小挖掘机

Pandas-Series知识点总结

1、Series创建 根据list pandas有两种主要的数据结构,第一种是Series,是一种类似于一维数组的数据结构,它由一组数据以及一组与之相关的数据标...

2413
来自专栏Brian

Pandas进阶之数据规整化

---- 概述 在Pandas基本使用简单了介绍了一下Pandas的基本使用和用法,大家如果没有一点基础的同学可以先看一下那篇文章。今天我们来讲解一下Panda...

2593
来自专栏编程

python及numpy,pandas易混淆的点

初接触python觉得及其友好(类似matlab),尤其是一些令人拍案叫绝不可思议的简单命令就可以完成非常复杂的计算,但是真正接触一下就发现,python比ma...

1975
来自专栏云霄雨霁

无向图----无向图的实现

1460
来自专栏海天一树

小朋友学数据结构(16):基于邻接矩阵的的深度优先遍历和广度优先遍历

这两个图其实是一样的,只是画法不同罢了。第一张图更有立体感,第二张图更有层次感,并且把A点置为顶点(事实上图的任何一点都可以做为顶点)。

895

扫码关注云+社区