图的基本介绍

图的定义

1.基本概念

• 在图中，顶点之间的关系可以是任意的，任意两个元素之间都可能相关
• 顶点的前驱和后继个数无限制

2.定义

• 图是一种：数据元素间存在多对多关系的数据结构
• 加上一组基本操作构成的抽象数据类型
• 可以表示为：G＝(V, VR)
  • 其中V 是顶点的有穷非空集合；
  • VR 是顶点之间 关系的有穷集合，也叫做弧或边集合。
  • 弧是顶点的有序对，边是顶点的无序对。

3.基本术语

• 顶点：图中的数据元素（顶点）
• 弧：连接两个顶点之间的一条边（有向图存在弧头与弧尾）
  • 用有序对 表示
• 边：无向图中连接两个点之间的边
  • 用无序对 (v, w) 表示

4.关于度

• 度：无向图的顶点向外连边的数量
• 入度：有向图顶点以其为弧的终点的弧的数量（连出去的）
• 出度：有向图顶点以其为弧的终点的弧的数量（连过来的）

5.简单路径与简单回路

• 简单路径：序列中顶点（两端点除外）不重复出现的路径。
• 简单回路：除了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路

6.生成树和生成森林

• 生成树：n个顶点的连通图有n-1条边
• 生成森林：对于非连通图，其每个连通分量可以构造 一棵生成树，合成起来就是一个生成森林。

图的分类

1.完全图

• 每两个顶点之间都存在一条边的图

• 若每两个顶点之间都存在一条弧，则为有向完全图

  

2.稀疏图与稠密图

• 稀疏图：含有很少条边（弧）的图（点数与边数相近）
• 稠密图：含有很多条边（弧）的图（边数远大于点数，接近完全图）
• 网：带权的图

3.子图与邻接点

• 子图：如果图 G = (V, E) 和 G´= (V ´, E´)满足： V ´属于 V 且 E´属于 E，则称 G´为G 的子图。

• 邻接点：

  • 对于无向图来说：

    • G=(V,E)如果(a,a')属于E，则两个顶点互为邻接点，两点相邻接
    • 通俗的讲就是无向边两端点互为邻接点，互相邻接

  • 对于有向图来说：

    • G=(V,E)如果属于E，则称顶点a邻接到a'，顶点a'邻接自a
    • 通俗的讲就是弧的起点邻接到终点，终点邻接自起点

4.连通图与联通分量

• 连通图：图中的任意两个点之间都是联通的
• 联通分量：无向图中的极大联通子图
• 非连通图：有 n 个顶点和小于 n-1 条边的图