6.图
图是一种复杂的非线性结构. 在图形结构中, 结点之间的关系可以是任意的.
若每条边都没有方向, 则该图为无向图.
若图中每条边都是有方向的, 则该图为有向图. 连接两个结点的边则为有向边. 有向边又称为弧, 边的起点称为弧尾, 终点称为弧头.
边两端的结点互为邻接点, 或称它们彼此相邻接.
无向图边数的取值范围是 0~n(n-1)/2, 具有 n(n-1)/2 个边的无向图称为 无向完全图, 此时, 任意任意两个结点都有边相连.
例如, 具有 5 个结点的图, 则边数最大值为 4+3+2+1=10.
有向图边数的取值范围是 0~n(n-1), 具有 n(n-1) 个边的有向图称为 有向完全图.
顶点的度即以该顶点为端点的边的数目, 对于有向图, 分为入度 (以顶点为终点的入边数目) 和出度 (以顶点为起点的出边数目).
无论无向图还是有向图, 边数均等于 所有边的度数之和的一半.
如果沿着图中的边可从顶点 P 到顶点 Q, 则称存在一条路径, 且这两个顶点是 连通 的. 如果除了起点和终点可为同一个顶点外,
其余顶点均不相同, 称为 简单路径. 若一条简单路径的起点和终点为同一个顶点, 则称该路径为回路或环.
如果无向图中任意两个顶点都连通, 称无向图为连通图. 无向图的极大连通子图称为连通分量, 显然, 任何连通图的连通分量只有其自身.
而非连通图的无向图有多个连通分量. 
如果有向图中任意两个顶点都连通, 则称有向图为强连通图. 有向图中的极大连通子图称为强连通分量. 
若在边上标上具有某种意义 (距离, 时耗等) 的数值, 该数值称为该边的权. 带权的图称为带权图. 带权的连通图称为网络. 
顺序存储: 邻接矩阵是表示图中顶点之间相邻关系的矩阵. 矩阵中对于 a[i][j], 如果其值为 1 则顶点 i, j 有边相连, 为
0 则没有边.
- 无向图的邻接矩阵是按主对角线对称的
- 有向图可用两个邻接矩阵, 一个表示出边, 一个表示入边
- 带权图中只要把
1换成权值,0换成无穷大即可
通常还需要使用一个一维数组存储顶点信息.
链式存储: 类似树中的孩子链表法, 把所有邻接于顶点 v 的顶点链成一个单链表, 这个单链表称为顶点 v 的 邻接表.
为每个邻接表增设表头结点, 并使用一个一维数组存储起来, 这个数组就构成了图的邻接表表示.
遍历图是求解图的连通性, 图的拓扑顺序等算法的基础.
深度优先搜索 (Depth First Search, DFS): 类似于树的前序 (先根) 遍历. 按此得到的顶点序列称为图的 DFS 序列: 
- 首先任选一个初始出发点
v, 并将其标记为已访问 - 然后依次从
v出发搜索每个邻接点w, 若w未曾访问, 则以w作为新的出发点, 继续深度优先遍历. 直到图中所有和v有路径相通的顶点都被访问到. 若此时图中仍有顶点未被访问:- 则另选一个未曾访问的顶点作为起点, 重复上述过程 (递归实现)
- 使用一个栈保存被访问过的结点, 通过栈回退到访问过的但尚有未访问过邻接点的顶点, 从该顶点出发重复上述过程 (栈实现)
广度优先搜索 (Breadth First Search, BFS): 类似于树的按层次遍历. 按此得到的顶点序列称为图的 BFS 序列: 
- 首先访问出发点
v, 接着依次访问v的所有未被访问过的邻接点v1,v2, ...vn, 并均标记为已访问 - 然后再按照
v1,v2, ...,vn的次序, 访问每个顶点的所有未曾访问过的顶点并均标记为已访问, 以此类推 - 直到所有和
v有路径相通的顶点都被访问过
因为先被访问的顶点, 其邻接点也先被访问, 符合队列先进先出特性. 实现时可使用一个队列, 依次记住被访问过的顶点.
DFS 和 BFS 遍历过程中, 为了避免顶点的重复访问, 设一个布尔数组 visited[0..n-1] 记录某结点是否已访问.
在图论中, 常常将树定义为一个无回路的连通图. 一个图的极小连通子图恰为一个无回路的连通图. 即若添加一条边就会出现回路, 若去掉一条边就成为非连通图.
生成树是连通图中的包含图中所有顶点的一个极小连通子图 (边最少). 具有 n 个顶点的生成树有且仅有 n-1 条边, 但有 n-1
条边的图不一定是生成树.
因为 DFS 和 BFS 对图中的 n 个顶点都仅访问一次, 因此除初始出发点外, 其余 n-1 个顶点的访问一共要经过 n-1 条边, 这
n-1 条边将 n 个顶点连接成包含图中所有顶点的极小连通图, 即得到一个生成树. 其源点就是生成树的根. 并分别称为 DFS
生成树和 BFS 生成树.
从连通图的观点出发, 针对无向图而言, 生成树又可定义为: 若从图的某顶点出发, 可以系统的访问到所有顶点, 则遍历时经过的边和所有顶点构成的子图, 称为该树的生成树. 此定义对有向图同样适用.
一个图可有不同的生成树. 对于带权图, 把权值最小的生成树称为最小生成树 (Minimum Spanning Tree, MST).
构造 MST 的算法, 多数利用了如下的 MST 性质:
假设
N=(V, {E})是一个连通网,U是顶点集V的一个非空子集, 若(u, v)是一条具有最小权值的边, 其中u ∈ U,v ∈ V-U, 则必存在一颗包含边(u, v)的 MST.
Prim 算法: 不断把扩张已有的 MST. 
- 假设
G=(V, E)是一个具有n个顶点的连通网,T=(U, TE)是G的 MST, 其中U是T的顶点集,TE是T的边集,U和TE初值均为空 . - 首先从
V中任取一个顶点v1, 将它并入U中, 此时U= {v1}. 然后只要U是V的真子集, 就从那些一个端点已在T中, 另一个端点仍在T外的所有边中, 找一条最短 (权值最小) 边, 假定为(vi, vj), 其中vi ∈ U,vj ∈ V-U, 并把该边和顶点vj分别并入TE和U. - 如此进行下去, 直到
n-1次后把所有顶点都并入到T的顶点集U中
Kruskal 算法: 不断合并最小边. 
- 假设
G=(V, E)是一个有n个顶点的连通网,T=(U, TE)是G的 MST,U的初值等于V,T的初始状态是只含有n个顶点而无边的森林T=(V, ∅) - 将
G中的边按权值从小到大依次选取E中的边- 若选取的边使
T不形成环路, 则并入TE - 若形成环路, 则舍弃
- 若选取的边使
- 如此进行直到
TE中包含n-1条边为止
由于一个网中会有权值相同的边, 从不同点出发可以得到不同的 MST.
从一个顶点到另一个顶点路径中, 所经边的权值之和最小的路径即最短路径.
- 单源最短路径问题: 求从源点到图中其余各顶点的最短路径
- 多源最短路径问题: 可用每个顶点作为源点调用一次单源最短路径问题算法求解
Dijkstra 算法 求单源最短路径: 按路径长度递增顺序产生各顶点的最短路径.
- 设有向图
G=(V, E), 其中V={1, 2, ..., n}.cost表示G的邻接矩阵,cost[i] [j]表示有向边<i, j>的权. 若不存在有向边<i, j>, 则cost[i][j]的权为无穷大. 设S是一个集合, 其中每个元素表示一个顶点, 从源点到这些顶点的最短距离已经求出. 设v1为 源点,S初始只包含v1. 数组dist记录从源点到其他各顶点当前的最短距离, 其初值为dist[i]=cost[v1][i](i=2, ..., n) - 从
S之外的顶点集合V-S中选出一个顶点w, 使dist[w]的值最小. 从源点到达w只通过S中的顶点, 把w加入集合S并调整dist中记录的距离, 即从原来的dist[v]和dist[w]+cost[w][v]中选出较小值作为新的dist[v] - 重复上述过程, 直到
S中包含V中其余顶点的最短路径
算法的最终结果为:
-
S记录了从源点到该顶点存在最短路径的顶点集合 -
dist记录了从源点到V中各顶点之间的最短路径长度 -
path是最短路径的路径数组, 其中path[i]表示从源点到顶点i的最短路径上顶点的前趋顶点
如给定下图中的有向图:
使用 Dijkstra 算法过程如下: 
把顶点表示活动, 边表示活动先后关系的有向无环图 (DAG) 称为顶点活动图 (AOV 网). 所有的活动排成一个线性序列, 使得每个活动的所有前趋活动都排在该活动前面, 此序列就是拓扑序列. 求次序列的过程称为拓扑排序.
拓扑排序算法过程:
- 在图中选取一个没有前趋 (入度为零) 的顶点, 输出它
- 从图中删除该顶点及与该顶点有关的所有边
- 重复上述过程, 直到全部顶点都已输出, 或剩余顶点中没有入度为零的顶点为止
- 输出剩余顶点
对给定的 AOV 网, 应首先判定网中是否存在环. 检测的方法是对有向图构造其顶点的拓扑序列, 若网中所有顶点都在它的拓扑序列中, 则该 AOV 网必定不存在环.