php中图的概念以及存储的方法

这篇文章主要讲解了“php中图的概念以及存储的方法”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“php中图的概念以及存储的方法”吧!

图的概念

还记得我们学习树的第一篇文章时看到的那张关于树的图片吗?

在当时,我们就说过,图c不是一颗树,而是一个图。为什么呢?从树的定义我们可以看的出,树只能有一个根结点,平级之间不能有联系,可以有多个子结点。而图就不用遵守这些规则,图的特点就是结点之间都可以互相有联系。比如下图这样的都是图。

在上面所画的图中,图是b的箭头的,而图一的连接线是没有箭头的,像这样有明确的方向的指向的图就叫做有向图。而没有箭头的,也就是没有方向指向的图就叫作无向图。

我们先将目光移到图a - 1,其实它就是把图一个旋转了一下。大家能看出来了吗?如果忽略掉结点4和1之间的连线,那么它就是一颗树。是不是和我们上面关于树的图中的图c的概念一致了。

关于图的比较正式的官方定义是:

图G(图)由两个集合V和E组成,记为G=(V, E),其中V是顶点的有穷非空集合,E是V中顶点的有穷集合,这些顶点偶对称为边。

在有向图中,连接两点的那个线段,从开始的结点到指向的那个结点可以记为& lt; x, y>灵活;x, y>和& lt; y, x>是两个不同的边,也可以叫作弧。根据图,我们可以看到这个图中有& lt; 1, 2比;、& lt; 2、1比;& lt; 1,3比;、& lt; 3、1比;& lt; 1 4比;、& lt; 4、1比;、& lt; 3、4比;、& lt; 4、3比;这几条边。而图b中,因为它是有向图,所以它的边只有& lt; 1, 2比;& lt; 1,3比;、& lt; 3、4比;、& lt; 4、1比;这四条。

是不是感觉在看上面的图片的时候还比较清晰,一看这个定义就一脸懵逼了?像这种定义,如果你是需要考试的同学,那就还是要背下来的。如果只是像我一起想以学习应用或者了解为主的话,就不用去死记硬背了.V就是结点,E就是这些这些结点之间的关系,两个顶点之间的关系,也就是图上的那些连接结点的线段就是边。

好的,这三个最最基础的概念搞明白了,我们就继续学习其它的和图有关的那一大车术语!

图的相关术语

首先,我们用n来表示图中顶点的数目,用E来表示边的数目,记住这两个代号。

<李>

(1)子图:假设有两个图G=(V, E)和舌鳎# 39;=(V # 39; E # 39;)如果V # 39;包含于V且e # 39;包含于E,则称舌鳎# 39;为G的子图

上图中右边的那些子图都是属于原图的子图,可以看出子图可以产生非常多的形态,有向图也是相同的概念,不过相对于无向图来说,有向图能够生成的子图更少一些,因为它的边是有方向的。

<李>

(2)无向完全图和有向完全图:对于无向图,若具有n (n - 1)/2条边,就是无向完全图。对于有向图,若具有n (n - 1)条孤,就称为有向完全图。(参考完全二叉树)

其实完全图的概念就是图中所有相邻的结点都有边能够连结在一起。

对于有向图来说,虽说边是有方向的,当然我们也可以定义一个来回的方向,比如& lt; 1, 2比;和& lt; 2、1比;,在有向图中我们就要画上两个相反方向的箭头表示可以从1到2也可以从2到1。而无向图中则是用一个边来代替这两个边的概念了,本身的那一条没有箭头方向的边就是双向的。

<李>

(3)稀疏图和稠密图:有很少条边或孤(如e <李>

(4)权和网:在实际应用中,每条边或孤可以标上具有某种意义的值,就像地图上的距离一样,这些数值就称为权。带权的图就可以称为网

最上方的的图片上图a和图b - 1的边上的数字代表的就是权重。这两张图就可以称为网图。权重的概念我们后面在讲相关的算法时会学习到,从这两张图中,我们其实就可以很明显的看的出,如果要从结1点走到结点4的话,并不是直接走& lt; 1, 4比;这条边,而是走& lt; 1, 3比;、& lt; 3、4比;这条路线更快些。

php中图的概念以及存储的方法