数据结构之图

图

1. 图的定义

图（graph） 是由一些点（vertex） 和这些点之间的连线（edge） 所组成的；其中，点通常称为顶点（vertex），而点到点之间的连线通常称之为边或者弧（edge）。通常记为G=（V,E）；

要注意的是：线性表可以是空表，树可以是空树，图不可以是空图，图可以没有边，但是至少要有一个顶点。

2. 图的组成

图由两种类型的元素组成，顶点和边，有时候，有向图的边也称为弧。

• 顶点代表对象，边则建立起对象之间的关系或关联。
• 入度就是进入该顶点边的数目，出度就是离开这个顶点边的数目，有向图的度就是入度加出度。
• 边是顶点之间的逻辑关系表示，边集可以是空的

3. 图的分类

• 有向图和无向图。

  • 有向图中，边是由两个顶点组成的有序对，具有特定的方向。形象地说，有向图可以由顶点和带方向的箭头所组成的圈绘制出来。
  • 无向图中，边是没有方向的，因此，无向图的边就直接用线段来代替箭头表示

• 完全图
  

  • 完全图如果任意两个顶点之间都存在边叫完全图，而有向的边叫有向完全图。
  • 当一个图接近完全图时，则称它为稠密图（Dense Graph），而当一个图含有较少的边时，则称它为稀疏图。

• 连通图
  

  • 无向图中，两顶点有路径存在，就称为连通的。若图中任意两顶点都连通，同此图为连通图。

• 无权图和带权图
  

  • 对图中的边赋予具有一定意义的数值(路程、费用等等)的图称为带权图

4. 图的存储结构

• 邻接矩阵
  

  • 邻接矩阵用两个数组保存数据。一个一维数组存储图中顶点信息，一个二维数组（邻接矩阵）存储图中边的信息。

  • 顶点v1 和顶点v3 之间存在一条边， 则称顶点v1 和3 互为邻接点。

  • 有向图邻接矩阵
    

  • 无向图邻接矩阵
    

  • 0 表示这两个顶点之间没有边，1 表示有边

  • 对应行非0元素的个数是出度；对应列非0元素的个数是入度

  • 优点： 可以快速判断两个顶点之间是否存在边，可以快速添加边或者删除边。

  • 缺点： 由于存在n个顶点的图需要n*n个数组元素进行存储，当图为稀疏图时，使用邻接矩阵存储方法将会出现大量0元素，这会造成极大的空间浪费。

  • 实现代码

5. 深度优先搜索

• 深度优先搜索在搜索过程中每当访问到某一个顶点后，需要递归地访问此顶点的所有未访问过的相邻顶点。因而，这种搜索将尽可能深地持续探索，直到无法继续为止。

6. 广度优先搜索

• 广度优先搜索在进一步探索图中的顶点之前，先访问当前顶点的所有邻接顶点。

最小生成树

• Kruskal 算法
  
  • 此算法可以称为“加边法”，初始最小生成树边数为0，每迭代一次就选择一条满足条件的最小代价边，加入到最小生成树的边集合里。
• Prim 算法
  
  • 此算法可以称为“加点法”，每次迭代选择代价最小的边对应的点，加入到最小生成树中。算法从某一个顶点A开始，逐渐长大覆盖整个连通网的所有顶点。