讲透学烂二叉树(一)：图的概念和定义—各种属性特征浅析

树和图的概念

图是一种特殊的数据结构，由点和边构成，它可以用来描述元素之间的网状关系，这个网状没有顺序，也没有层次，就是简单的把各个元素连接起来。

图的概念和基本性质

图（graph）：图（graph）由边（edge）的集合及顶点（vertex）的集合组成。通常记为：G=(V,E)。对于两个图G和G’，如果G’的顶点集合与边集合均为G的顶点集合与边集合的子集，那么称G’是G的子图。子图实际上就是一张图里面小一点的图，也可以是点，不难理解。

图常用来表示“多对多”的关系，如常说的：六度空间理论（Six Degrees Separation）

顶点（vertex）的属性：

• 度数（degree），与该顶点相关联的总边数，一个图G的总度数d(V)等于总边数2倍：2E。当图的边具有方向时，一个顶点又分为出度（out-degree）和入度（in-degree），出度是以该顶点为起点的边数，入度是以该顶点为终点的边数。

• 阶数（order），图G中顶点集V的大小为G的阶数。

边又称为线（line）或弧（arc），边(u,v)中表示u和v邻接（adjacent），(u, v) ∈ E，

边（edge）的属性：

一条边是一个顶点对(u,v)，u, v ∈ V，按照图的顶点对是否有序，顶点对有序的图称为有向图（directed graph, digraph），此时边(u,v)和(v,u)是两条不同的边，顶点对无序的图称为无向图（undirected graph），此时边(u,v)和(v,u)是两条相同的边，无向图可看作一个特殊的有向图

具有成分的边包含：权（weight）、值（cost/value），此时图由可分为有权图（weighted graph）和无权图（unweighted graph），无权图可以看作是所有边权值相同的有权图。

路径（path），一条路径是一个顶点序列u1, u2, u3, …, un，(ui, u(i+1)) ∈E，1<=i<n。路径长等于路径的边数：n-1，不包含边的路径长为0。

简单路径：路径上所有顶点互异，起点和终点可以相同

环或圈（cycle），此时u1=un，而且路径长至少为1，有向图(u,v)和(v,u)是一个圈，无向图(u,v)和(v,u)通常不被认为是一个圈。其中无圈图（acyclic graph）中没有圈，无圈有向图又称为DAG（directed acyclic graph）

• 自环边（self loop），两个顶点都相同的边。

• 重边或平行边（parallel edges），连接两个顶点的边数超过一条，又称为多重边（multiple edges）

连通图（connected graph），无向图中每个顶点到任意顶点都存在一条路径，连通的有向图称为强连通（strongly connected），非连通的有向图，去掉方向其基础图（underlying graph）是连通的，则成为弱连通的（weakly connected）

完全图（complete graph），图中任意一对顶点都存在一条边

稀疏图（sparse graph），每个顶点的度数较小的图

图的基本基本概念

• 顶点的度：无向图中连着顶点的边的数目。

• 顶点的入度和出度：有向图中，以这个顶点为起点的边的数量称为这个顶点的出度；以这个顶点为终点的边称为这个顶点的入度。

• 边权：边的费用，可以形象的理解为“过路费”。对于一张存在边权的图，我们称为“带权图”。

• 连通：如果图中两点U,V之间存在一条由U经过若干边、点到达V的路径，则称U，V是连通的。

• 回路：起点和终点相同的路径，称为“回路”或“环”。另外，不存在环的有向图称为Directed Acyclic Graph(DAG)。

• 完全图：每个点都与其它所有的点有连边的图。

• 无向图：图的边没有方向，可以双向。
  

• 有向图：图的边有方向，只能按箭头方向从一点到另一点。

• 网络：带权重的图

• 连通：如果从v 到w存在一条（无向）路径，则称v和w是连通的

• 路径：v到w的路径是一系列顶点的集合，其中任意一对相邻的顶点间都有图中的边。

• 路径的长度：是路径中的边数（如果带权，则是所有边的权重和）。如果v和w之间的所有顶点都不同，则称简单路径

• 连通图：图中任意两顶点都连通

• 连通分量：无向图的极大连通子图

• 极大顶点数：再加一个顶点就不连通了

• 极大边数：包含子图中所有顶点相连的所有边

• 强连通：有向图中顶点v和w之间存在双向路劲，则称v和w是强连通的

• 强连通图：有向图中任意两顶点均强连通

• 弱连通图：不符合强连通图的条件，但是若是将边的方向都去掉，如果是连通的，则称为弱连通图

• 强连通分量：有向图的极大强连通子图

图的简单应用

图的应用很广泛，这里举几个简单的例子。

• 航空系统：顶点表示机场，边表示时间、距离或飞行的费用，一般最好有强连通的航空系统，另外常见的需求问题有：求任意两个机场的最佳航线。

• 交通流：顶点表示街道的交叉口或红绿灯点，边表示速度限度或车辆容量，这时可以求最可能参数交通瓶颈的位置，或找出一条最短路。

• 社交网络：顶点表示用户，用户的活动、推荐或好友代表边，这样可以表示一个完整的社交用户网络。

• 电商推荐系统：顶点表示用户已浏览、收藏、购物过等相关的商品，边表示两个商品的相似性，可表示为有权图，权值为相似性的大小。

另外图论又可用于研究物理学和化学中的分子

图的遍历

1. 深度优先搜索（Depth Firsh Search, DFS)：走一步，看一步，走不通后返回到上一个能走通的结点

2. 广度优先搜索（Breadth First Search, BFs)：出队一个，访问一圈，访问的同时入队，相当于树的层序遍历（计划性非常强，个人感觉用这种遍历方式更好一些）

本系列主要讲二叉树，关于图，推荐阅读文章有：

• 数据结构与算法之图的概念、存储结构及遍历方式 https://www.cnblogs.com/ivy-zheng/p/10995510.html

• 图的概念、存储及遍历 https://blog.csdn.net/qq_39914766/article/details/90182084

• 图论(graph theory)算法原理、实现和应用全解 www.srcmini.com/1635.html

转载本站文章《讲透学烂二叉树(一)：图的概念和定义—各种属性特征浅析》,
请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8281.html