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

树和图的概念

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

图的概念和基本性质

图(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),无向图中每个顶点到任意顶点都存在一条路径,连通的有向图称为强连通(spanly 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):出队一个,访问一圈,访问的同时入队,相当于树的层序遍历(计划性非常强,个人感觉用这种遍历方式更好一些)


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

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

  • 图的概念、存储及遍历 blog.csdn.net/qq_39914766…

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




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


以上是 讲透学烂二叉树(一):图的概念和定义—各种属性特征浅析 的全部内容, 来源链接: utcz.com/a/21282.html

回到顶部