图的定义

图是由定点的有穷非空集合和顶点之间边组成，通常表示为G（V,E），其中G表示一个图，V表示图G的顶点，E表示图G边的集合

图的性质

线性表我们把数据元素叫做做元素，树中我们将数据元素叫做结点，在图中的数据元素我们叫做顶点（Vertex）

线性表可以没有元素，叫空表。树可以没有结点，做空树。

线性表中，相邻元素之间具有线性关系。在树中，相邻两层结点具有层次关系。而图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空集。

图的分类

• 无向图
  直观来说，若一个图中每条边都是无方向的，则称为无向图。
  无序对(vi，vj)和(vj，vi)表示同一条边。
  

  无向图.png
  
  在无向图中，若每两个顶点都有边，则称该图为无向完全图。
  
  无向完全图.png

• 有向图
  若从顶点Vi到Vj的边有方向，则这条边为有向边，也称为弧。用序偶<Vi,Vj>表示，Vi称为弧尾（Tail），Vj称为弧头（Head）。
  如果图中任意两条边的都是有向边，则称该图为有向图。

  
  
  有向图.png

在有向图中，若每两个顶点都有互为相反方向的两条有向边，则称该图为有向完全图。

• 图的权
  有些图的边或者弧度具有与他相关的数字，这种与图的边或者弧相关的数字叫做权。

image.png

• 连通图

在一个无向图 G 中，若从顶点i到顶点j有路径相连（当然从j到i也一定有路径），则称i和j是连通的。图中任意两个顶点Vi，Vj都是联通的，则称图G为连通图

注意 ：是有路径，不是有边。

image.png

• 度

无向图顶点的边数叫度，有向图顶点的边数叫出度和入度

image.png

image.png

图的数据存储结构

不能用简单的顺序存储结构表示，也不能用多重链表结构，因为有空间的浪费。

• 邻接矩阵

  
  
  image.png
  
  

  在无向图中，边是相当于两个顶点相互指向，邻接矩阵关于斜边对称

  
  
  image.png

使用数组的形式来储存数据

• 邻接表
• 十字链表（有向图）
• 邻接多重表（无向图）