数据结构与算法复习笔记——图
图
- 有向图:弧<v1,v2>→弧带权:有向网→n个顶点含有n(n-1)条边:有向完全图
- 无向图:边(v1,v2)→边带权:无向网→n个顶点含有n(n-1)/2条边:完全图
- 稀疏图:e<nlogn,反之则为稠密图
一些基本概念
度:
- 度TD(v):有向图中:ID+OD;无向图:关联边数
- 入度ID(v):有向图,指向顶点v
- 出度OD(v):有向图,指出顶点v
路径:
- 路径长度:路径上边的数目
- 简单路径:顶点不重复出现
- 简单回路:第一个顶点和最后一个顶点相同的路径
连通图:
- 连通图:无向图中任意两个顶点间都有路径相通
- 强连通图:有向图
- 连通分量:非连通图中极大联通子图
- 强连通分量:非强连通图极大强连通子图
树:
- 生成树:连通图由n-1条边n个顶点构成的极小连通子图→生成树不唯一
- 生成森林:非连通图各个连通分量的生成树
- 有向树:一个有向图恰有1个顶点入度为0、其余顶点入度为1
图的存储结构
数组(邻接矩阵)存储表示
无向图的邻接矩阵是对称阵,有向图不一定
考点
有向图顶点vi:
- 入度:ID(vi)=Σ_{j=0} ^{n-1}A[j][i]
- 出度:OD(vi)=Σ_{j=0}^{n-1}A[i][j]
邻接表存储表示
将邻接矩阵用n个单链表代替。
有向图的十字链表存储表示
其中顶点的第一个指针域指向流入结点。第二个指针域指向流出结点。
考点:十字链表的画法
先画出每个顶点流出的弧的链表,然后连接流入弧的链表。
无向图的邻接多重表存储表示
图的遍历
每个顶点访问且仅被访问一次。
深度优先搜索
一条路走到黑,先沿着一个路径,深度不断增加,直至该路径没有未被访问的结点,再向后退,寻找可访问的路径。
深度优先搜索生成树:访问时经过的顶点和边构成的子图
可以用于判断顶点间是否存在最短路径,或者图是否为连通图。
广度优先搜索
从某个顶点出发,先访问深度为1的顶点,再访问深度为2的顶点…直至所有顶点都被访问到。
可用于求两顶点间最短路径/
最小生成树问题
Prim算法
选择距离最近的点,之后更新到各点的距离,已被读取的则距离置为0。
Kruskal算法(适合稀疏图)
将所有边的权重按升值排序,选取权重最小的边,若构成回路,则舍去。
有向无环图
AOV网构造拓扑排序序列
选取AOV网中入度为0的结点,并将其从网中删除。
若图中有剩余顶点未被删除,则图中有回路,不是AOV网
AOE网及关键路径
- 顶点:事件(9个事件)
- 路径:活动(11项活动)
- 事件最早发生时间:ve[k]=max{ve[j]+dut(<j,k>)},指向vk的所有弧的最长路径。(加上最长的)
- 事件最迟发生时间(在保证完成结点最早发生的前提下):vl[i]=min{vl[k]-dut(<i,k>)},vk指出的所有弧的最短路径。(减去最长的)
- 活动最早发生时间:发出活动事件的最早发生事件。
- 活动最迟发生时间:活动指向事件的最晚发生事件减去活动所需事件。
- 活动延迟时间:活动最迟发生时间减去活动最早发生时间。
- 关键活动:延迟时间为0的活动
- 关键路径:路径上所有活动均为关键活动。
最短路径
迪杰斯特拉算法——一到多
适用于静态网络,边上的权值不能为负数。
类似Prim算法。
弗洛伊德算法——每一对顶点
分别以A、B、C作为转车,寻找最短路径。