java图谱基础讲解

大家好，我是讯享网，很高兴认识大家。

8.1.0 图的应用场合

8.1.1 图的定义

图G（Graph）由两个集合V（Vertex）和E（Edge）组成，记为G=(V，E)。

V是顶点的有限集合，记为V(G)。

E是连接V中两个不同顶点（顶点对）的边的有限集合，记为E(G)。

思考：上面导航地图中哪些是顶点，哪些是边？顶点应该存储哪些信息？而边又要存储哪些信息？（具体参见视频）

抽象数据类型图的描述

8.1.2 图的基本术语

说明：图的基本术语有很多，大家在学习过程中能理解即可，不需要进行大量的记忆。遇到图的实际应用算法的时候，再来回顾与深入理解这些术语。

无向图：如果任意两个顶点构成的偶对(vi,vj)∈E是无序的，即顶点之间的连线是没有方向的，则称该图为无向图(Undigrpah)

有向图：如果任意两个顶点构成的偶对<vi,vj>∈E是有序的，即顶点之间的连线是有方向的，则称该图为有向图(Digrpah)

多重图：数据结构中的图一般不重复出现一条边，如果允许重复边出现，这样的图称为多重图（Multigraph），如一个无向图中顶点1和2之间出现两条或两条以上的边。本章中讨论的图均指非多重图。

顶点(Vertex)：图中的数据元素vi,vj

边(Edge)：无向图中两个顶点vi,vj之间的直接连线；用顶点的无序偶对(v，w)来表示，顶点v和顶点w互为邻接点

弧(Arc)：有向图中两个顶点vi,vj之间的直接连线；用顶点的有序偶对<vi,vj>来表示；有序偶对的第一个结点vi被称为始点(或弧尾Tail)，有序偶对的第二个结点vj被称为终点(或弧头Head)，若<v，w>是一条弧，则称顶点v邻接到w，顶点w邻接自v

无向完全图：在一个无向图中，如果任意两顶点都有一条直接边相连接，则称该图为无向完全图(Undereted Complete Graph)。

有向完全图：在一个有向图中，如果任意两顶点之间都有方向互为相反的两条弧相连接，则称该图为有向完全图(Directed Complete Graph)。

度(degree)：依附于某顶点v的边数，通常记D(v)

入度(indegree)：有向图中，以顶点v为终点的弧的数目称为顶点v的入度，记为ID(v)

出度(outdegree)：有向图中，以顶点v为始点的弧的数目称为顶点v的出度，记为OD(v)

权(weight)：图中的边或弧附带的与边相关的数值信息。

带权图或网络：每条边或弧都带权的图

路径:在无向图G=(V，E)中，从顶点vp到顶点vq之间的路径是一个顶点序列(vp=vi0,vi1,vi2,…, vim=vq),其中，(vij-1,vij)∈E(1≤j≤m)。若G 是有向图则路径也是有方向的，顶点序列满足<vij-1,vij>∈E (1≤j≤m)，路径上边的个数称为路径长度。

简单路径：序列中顶点不重复的路径。

回路：起点和终点相同的路径。

简单回路：除第一个和最后一个顶点外其他顶点不重复出现的回路。

子图：若图G=(V，E)，G'=(V'，E')，如果V'V 且E'  E ，则称图G'是G的子图。

连通：在无向图中，如果从一个顶点vi到另一个顶点vj(i≠j)有路径，则称顶点vi和vj是连通的。

连通图：如果无向图中任意两个顶点都是连通的。

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

强连通图：在有向图中，对图中任意一对顶点vi 和vj (i≠j)，若从顶点vi到顶点vj和从顶点vj到顶点vi均有路径。

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

生成树：是一个极小的连通子图，包含图中全部顶点，和最少的边。

站内视频：

8.1.1 图的定义