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 条评论
登录 后参与评论

相关文章

来自专栏张善友的专栏

如何去理解 拓扑排序算法

查看Castle的代码,在Castle.Core中内部的数据结构采用图,排序使用的拓扑排序算法:        对于一条有向边(u,v),定义u < v;满足所...

19910
来自专栏zaking's

用js来实现那些数据结构15(图01)

1434
来自专栏小樱的经验随笔

邻接矩阵存储有向图(详解)

邻接矩阵存储有向图 【输入描述】   输入文件包含多组测试数据,每组测试数据描述了一个无权有向图。每组测试数据第一行为两个正整数n和m,1<=n<=100,1<...

2599
来自专栏数据结构与算法

Kosaraju算法详解

Kosaraju算法可以求出有向图中的强连通分量个数,并且对分属于不同强连通分量的点进行标记。它的算法描述较为简单: (1) 第一次对图G进行DFS遍历,并在...

3356
来自专栏Android机动车

数据结构——图相关概念

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

742
来自专栏恰同学骚年

数据结构基础温故-5.图(上):图的基本概念

前面几篇已经介绍了线性表和树两类数据结构,线性表中的元素是“一对一”的关系,树中的元素是“一对多”的关系,本章所述的图结构中的元素则是“多对多”的关系。图(Gr...

662
来自专栏有趣的Python

15-数据结构探险系列-图篇数据结构探险之图篇

图的存储结构:邻接矩阵(数组);邻接表(链表)有向; 十字链表(链表)有向;邻接多重表(链表)无向

573
来自专栏李家的小酒馆

图论基本知识

图 图的基本概念 图示一个复杂的结构,节点之间的关系可以是任意的,图中的任意两个元素之间都可能相关。 ? 图分为有向图和无向图,无向图为两个节点之间互相可以到达...

1860
来自专栏IT可乐

Java数据结构和算法(十五)——无权无向图

  前面我们介绍了树这种数据结构,树是由n(n>0)个有限节点通过连接它们的边组成一个具有层次关系的集合,把它叫做“树”是因为它看起来像一棵倒挂的树,包括二叉树...

2945
来自专栏python读书笔记

《python算法教程》Day2 - 图和树的基本数据结构图树

今天是读《python算法教程》的第2天,读书笔记内容为用python实现图和树的基本数据结构。 图 图的基本数据结构有两种,分别为邻接列表和邻接矩阵。 现根...

1985

扫描关注云+社区