数据结构 -- 图 定义与分类
参考链接–简书
参考链接–csdn
介绍
一个图就是一些顶点的集合，这些顶点通过一系列边结对（连接）。
顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
注意：顶点有时也称为节点或者交点，边有时也称为链接。
定义
图G由顶点集V和边集E组成，记为G=(V,E)，其中V(G)表示图G中顶点的有限非空集；E(G)表示图G中顶点之间的关系(边)的集合
注：图可以没有边，但是至少要有一个顶点
权重
边可以有权重（weight），即每一条边会被分配一个正数或者负数值。考虑一个代表航线的图。各个城市就是顶点，航线就是边。那么边的权重可以是飞行时间，或者机票价格。
方向
边可以是有方向的。有方向的边意味着是单方面的关系。一条从顶点 X 到 顶点 Y 的边是将 X 联向 Y，不是将 Y 联向 X。
以航班为例，从旧金山到阿拉斯加的朱诺有向边意味着从旧金山到朱诺有航班，但是从朱诺到旧金山没有
映射关系
多对多关系
无向图
边没有方向的图
定义
无向图G=<V,E>,其中：
- V是非空集合，称为顶点集
- E是V中元素构成的无序二元组的集合，称为边集
图形
有向图
一个有向图D是指一个有序三元组(V(D)，A(D)，ψD)，其中ψD)为关联函数，它使A(D)中的每一个元素(称为有向边或弧)对应于V(D)中的一个有序元素(称为顶点或点)对
定义
图形
注：有向图顶点分为 入度（箭头朝自己） 和 出度（箭头朝外）
简单图
在图中，若不存在顶点到其自身的边，且同一条边不重复出现，则称这样的图为简单图
定义
不包含平行边也不包含自环的图
平行边
在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边
在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点与终点相同(也就是它们的的方向相同)，称这些边为平行边
图形
完全无向图
定义
在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图
图形
有向完全图
定义
在有向图中，如果任意两个顶点之间都存在 方向互为相反 的两条弧，则称该图为 有向完全图