图的定义
图是由定点的有穷非空集合和顶点之间边组成，通常表示为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
使用数组的形式来储存数据
- 邻接表
- 十字链表（有向图）
- 邻接多重表（无向图）
