资阳市泰智网络公司
首页 | 联系方式 | 加入收藏 | 设为首页 | 手机站

产品目录

联系方式

联系人:业务部
电话: 00170-875377
邮箱:service@xtxymfj.com

当前位置:首页 >> 产品展示 >> 默认分类 >> 正文

算法导论之图算法--图的基本概念

详细信息:

是数据结构和算法学中最强大的框架之一(或许没有之一)。

用途:

1、用来表现所有类型的结构或系统

2、交通网络

3、通信网络

4、下棋游戏

5、最优流程

6、任务分配

7、人际交互网络

。。。。。。


下面首先介绍一下图论的基本概念,对其有基本了解之后再在实践中加深理解。

图是将各种模型抽象成一些顶点,这些顶点之间可以通过图的边实现连接,即vretexedge,如下图所示圆圈中的顶点和黑色的边:

一、顶点

电路图中电路元件、或者最近路径中的城市等抽象出来事物或对象。也称为节点、结点等

二、边

顶点之间的连线,表示顶点表示的事物或对象之间的关联。有有向边和无向边,对应有向图和无向图

三、同构

只要表示的顶点之间边的逻辑关系相同就是同一张图,也就是图的同构。与图的表现形式不同。不论表示边的线的粗细和阴影,顶点的颜色,下面两个图表示的同一个图


四、有向图和无向图Directed Graph/ Undirected Graph

顾名思义,有方向和无方向。这里是指图的边时候有方向。不需要考虑边上表明的数据,这里可以看到边是有特定的方向,即v1到v3是可以的,但是v3到v1就是不可以的。前面其他的图就是无向图


五、权重weight

如下图中边上标出的值,表示城市间的距离、或者代价等,可以为正数、也可以为负数(距离和价值不可以,但其他实际意义的时候可能存在)

六、路径、最短路径

在图中设定起点(城市)和终点(目的地城市),找出从起点到终点的一条路径,若权重为距离,可以找到最短的距离;若权重为代价,可以找到最低消费。如下图从S到t点的路径,上面数据表示权重


七 环loop

如上图的v1->v3->v2其实是个环

八 连通图、连通分量

所有顶点之间都存在通路,如下图下面的分成上下两部分,不是联通的


图虽然不是一个连通图,但它有多个连通子图:0,1,2顶点构成一个连通子图,0,1,2,3,4顶点构成的子图是连通图,6,7,8,9顶点构成的子图也是连通图,当然还有很多子图。我们把一个图的最大连通子图称为它的连通分量。0,1,2,3,4顶点构成的子图就是该图的最大连通子图,也就是连通分量。连通分量有如下特点:

1)是子图;
2)子图是连通的;
3)子图含有最大顶点数。
注意:“最大连通子图”指的是无法再扩展了,不能包含更多顶点和边的子图。0,1,2,3,4顶点构成的子图已经无法再扩展了。
显然,对于连通图来说,它的最大连通子图就是其本身,连通分量也是其本身。