基本概念
- 数据元素之间是一种多对多的关系，用罗辑边标识元素之间的关系；
- 线性表中数据称为
元素，树中将元素称为结点，图中数据元素称为顶点(vertex)，线性表可以为空表，树可以为空树，但是图不允许有空结点； - 顶点
有穷非空集合和顶点之间的边组成； - G(V,E) G: 表示一个图，V: 表示顶点集合，E: 表示边的集合；
简单图
- 不存在顶点到自身的边；
- 同一条边不重复出现；
- 是我们要讨论的图；
无向图
- 顶点之间边
无方向的边称为无向边(A,B)； - 图中任意两个顶点之间的边都是无向边，称该图为
无向图； - 无向图中，任意两个顶点都存在边，称该图为
无向完全图； - 无向完全图有
(n*(n-1))/2条边，n代表顶点数； - 无向图顶点的度TD：
- 和顶点相关的边的数目; TD=各顶点度的和；
- 边的数量 e=(1/2)*TD
有向图
- 顶点之间的边
有方向的边称为有向边或弧（Arc）<A,B>； - 图中任意两个顶点之间的边都是有向边，称该图为
有向图； - 图中任意两个顶点都存在方向
互为相反的两条弧，称该图为有向完全图； - 有向完全图有
n*(n-1)条边，n代表顶点数； - 有向图顶点的度TD是各个顶点入度数+出度数之和：
- 度（TD）= 入度（ID）+出度（OD）;
- 边的数量＝ID = OD;
网
- 与图的边或弧相关的数叫做
权； - 带权的图称为
网；
路径
路径长度：路径上的边或弧的数量；
回路或环（cycle）：路径中第一个顶点和最后一个顶点是
同一个顶点；简单路径：顶点不重复出现的路径；
简单回路（简单环）：除了第一个顶点和最后一个顶点之外，其他顶点不不重复的回路；
连通图：
- 无向图：
- 连通：两个顶点间存在路径，称为这两个顶点是连通的；
- 连通图：图中任意两个顶点都是连通的；
- 连通分量：极大连通子图；
- 子图
- 子图要连通
- 连通子图含有极大顶点数；
- 连通子图含有极大边数；
- 连通分量再加入一个原图顶点或边就不连通了；
- 有向图：
- 强连通图：图中任意顶点A,B A!=B, 存在A到B和B到Ａ的路径；
- 强连通分量：极大连通子图
生成树
- 无向图中连通并且有ｎ个顶点，n-1条边叫
生成树； - 有向图中一顶点入度为０，其他各个顶点入度为１的叫
有向树；
存储结构
邻接矩阵
- 一个一维数组存顶点；
- 一个二维数组存图中的边/弧的信息（邻接矩阵）；
- arc[1][3] = 0; v1到v3不存在边；
- arc[2][4] = 1; v2到v4存在边；
- 如果是网则 arc[i][j] = 权值；
- 无向图顶点vi的度＝矩阵中第ｉ行或第ｉ列中值的和；
- 有向图顶点vi的
入度＝矩阵中vi列的各数之和； - 有向图顶点vi的
出度＝矩阵中vi行的各数之和；
邻接表
- 对于边数相对较小的图，
邻接矩阵会存在浪费空间的情况； - 邻接表：顶点存在一个一维数组中；
- 无向图边表：某一顶点所有邻接点构成一个单链表；( 有向图分出边表和入边表（逆邻接表） )；
十字链表
- 把邻接表和逆邻接表整合在一起；
- 为
有向图设计； - 一维数组+单链表；
邻接多重表
- 优化无向表的邻接表结构；
- 同一条边在邻接表中用
两个结点表示； - 同一条边在邻接多重表中用
一个结点表示； - 一维数组+单链表；
边集数组
- 由两个一维数组构成，（一个存顶点信息，另一个存边的信息）；
- 适合对对边的处理；
