数据结构之图的基本概念

图

文章目录：

• 图的基本概念
• 图的存储结构
• 图的遍历
• 最小代价生成树
• 最短路径
• 拓扑排序
• 关键路径

文章将按照上述目录依次讲解

这一节主要谈第一部分：图的基本概念和相关术语

1.图的概念

图(Graph)是由顶点的有穷非空集合和顶点之间边的集合组成，通常表示为:G(V,E).其中，G表示一个图，V是G中顶点的结合，E是G中边的集合.

• 区分于线性表和树的结点，在图中数据元素称为顶点
• 线性表相邻的数据元素之间具有线性关系
• 树结构相邻两层的结点具有层次关系
• 而图结构中任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边表示，边集可以是空的。

2.相关术语

• 有向图和无向图:有序偶：<vi,vj>;无序偶(vi，vj)

• 弧：有向图的边；弧头，弧尾；

• 度：顶点的度，入度，出度。

• 有向完全图，无向完全图：

  • 有向图中有n个结点，则最多有n(n-1)条边(任意两个顶点都有两条边相连)，将具有n(n-1）条边的有向图称为有向完全图。
  • 无向图中有n个结点，则最多具有n(n-1）/2条边(任意两个顶点之间都有一条边)，将具有n(n-1)/2条边的无向图称为无向完全图

• 路径，简单路径

• 回路

• 连通，连通图，连通分量

• 简单图：

• 强连通图，强连通分量

• 权和网：带有权的图称为带权图，也称为网

• 极大连通子图，极大强连通子图，子图

• 稠密图，稀疏图：通常认为边或者弧数小于n*logn(n是顶点的个数)的图称为稀疏图，反之称为稠密图

• 连通图的生成树定义：一个连通图的生成树是一个极小的连通子图。

• 有向树

图的基本概念差不多就这些，下一讲是图的存储结构，内容更为丰富。
2020.7.28.