Lipsky

数据结构-图的概念

字数统计: 779阅读时长: 2 min
2019/11/25 Share

图的概念#

图 G 由顶点集 V 和边集 E 组成,记为 G=(V, E),其中 V(G) 表示图 G 中顶点的有限非集;E(G) 表示图 G 中顶点之间的关系(边)的集合。

注意:图不可以是空图,也就是说图中不能一个顶点都没有,但是边集可以为空

有向图#

边 E 是有向边的有限集合。入度和出度分别等于边数

无向图#

边 E 是无向边的有限集合。无向图的度之和为边数的两倍

简单图#

  • 不存在重复的边
  • 不存在顶点到自身的边

多重图#

图 G 中某两个结点之间的边数多余一条,又允许顶点通过同一条边和自己关联。多重图的定义与简单图相对。

完全图(简单完全图)#

  • 无向完全图:在无向图中,任意两个顶点之间都存在边。含有 n(n-1)/2 条边

  • 有向完全图:有向图中,任意两个顶点之间都存在方向相反的两条弧。含有 n(n-1) 条有向边

子图#

两个图 G = (V, E) 和 G’ = (V’, E’),若 V’ 是 V 的子集,且 E’ 是 E 的子集,则称 G’ 是 G 的子图

连通、连通图和连通分量#

  • 无向图中,若从顶点 v 到顶点 w 由路径存在,则称 v 和 w 是连通的。若图中任意两个顶点都是连通的,则为连通图。

对于边数 e:

  • e < n-1非连通图
  • e > n-1 有环
  • e = n-1 连通图

  • 极大连通子图:子图是无向图连通分量,极大要求该连通子图包含其所有的边

  • 极小连通子图:既要保持图连通,又要使得边数最少的子图

强连通图、强连通分量#

有向图中,从顶点 v 到 w 之间相互都有路径,则为强连通的。

生成树和生成森林#

连通图的生成树是包含图中全部顶点的一个极小连通子图。

若图中顶点数为 n ,则它的生成树含有 n-1 条边。

砍掉一条边,立马变成非连通图。

加上一条边,立马变成环

边的权和网#

图中,每条边都可以标上具有某种含义的数值,该数值成为边的权值。带权值的图称为有权图,或者网

稠密图、稀疏图#

|E|<|V|log|V| 时,为稀疏图

路径、路径长度和回路#

顶点 p 到 q 一条路径为 p 到 q 所经过的所有顶点。路径上边的数目为路径长度。

简单路径、简单回路#

路径序列中,顶点不重复出现的路径为简单路径。

除第一个顶点和最后一个顶点外,其余顶点不重复出现的回路称为简单路径。

距离#

v 到 w 路径存在,则此路径长度为其之间的距离,若不存在则记为 ∞

有向树#

顶点的入度为 0、其余顶点入度均为 1 的有向图。

CATALOG
  1. 1. 图的概念#
    1. 1.1. 有向图#
    2. 1.2. 无向图#
    3. 1.3. 简单图#
    4. 1.4. 多重图#
    5. 1.5. 完全图(简单完全图)#
    6. 1.6. 子图#
    7. 1.7. 连通、连通图和连通分量#
    8. 1.8. 强连通图、强连通分量#
    9. 1.9. 生成树和生成森林#
    10. 1.10. 边的权和网#
    11. 1.11. 稠密图、稀疏图#
    12. 1.12. 路径、路径长度和回路#
    13. 1.13. 简单路径、简单回路#
    14. 1.14. 距离#
    15. 1.15. 有向树#