58、数据结构与算法Python:图的基本概念及相关术语

图Graph的概念

图Graph是比树更为一般的结构, 也是由节点和边构成

实际上树是一种具有特殊性质的图

图可以用来表示现实世界中很多事物

道路交通系统、航班线路、互联网连接、或者是大学中课程的先修次序

   

一旦我们对图相关问题进行了准确的描述

就可以采用处理图的标准算法来解决那些看起来很艰深的问题

对于人来说,人脑的识别模式能够轻而易举地判断地图中不同地点的相互关联;但如果用图来表示地图,就可以解决很多地图专家才能解决的问题,甚至远远超越;互联网是由成千上万的计算机所连接起来的复杂网络,也可以通过图算法来确定计算机之间达成通讯的最短、最快或者最有效的路径。

术语表

顶点Vertex(也称“节点Node”)

是图的基本组成部分,顶点具有名称标识Key,也可以携带数据项payload

边Edge(也称“弧Arc”)

作为2个顶点之间关系的表示,边连接两个顶点;边可以是无向或者有向的,相应的图称作“无向图”和“有向图

权重Weight

为了表达从一个顶点到另一个顶点的“代价”,可以给边赋权;例如公交网络中两个站点之间的“距离”、“通行时间”和“票价”都可以作为权重。
*

路径Path

图中的路径,是由边依次连接起来的顶点序列;无权路径的长度为边的数量;带权路径的长度为所有边权重的和;如下图的一条路径(v3,v4,v0,v1)

  • 其边为{(v3,v4,7),(v4,v0,1),(v0,v1,5)}
    *

圈Cycle

圈是首尾顶点相同的路径,如下图中(v5,v2,v3,v5)是一个圈,如果有向图中不存在任何圈,则称作“有向无圈图directed acyclic graph: DAG”,后面我们可以看到如果一个问题能表示成DAG,就可以用图算法很好地解决。
*

图的定义

一个图G可以定义为G=(V, E)

其中V是顶点的集合, E是边的集合, E中的每条边e=(v, w), v和w都是V中的顶点;如果是赋权图,则可以在e中添加权重分量子图: V和E的子集
*

赋权图的例子: 6个顶点及9条边

有向赋权图,权重为整数
*

版权声明:本文不是「本站」原创文章,版权归原作者所有 | 原文地址: