5.图
图（Graph）是一种较线性表和树更为复杂的非线性结构。**在图结构中，对结点（图中常称为顶点）的前驱和后继个数不加限制，**即结点之间的关系是任意的。图中任意两个结点之间都可能相关。
图状结构可以描述各种复杂的数据对象。
图的应用极为广泛，特别是近年来的迅速发展，已经渗透到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中。
图 VS. 树
不一定具有一个根结点
没有明显的父子关系
从一个顶点到另一个顶点可能有多个（或0个）路径
很多问题都可以抽象成一个图结构，考虑如下三个例子：
将电影界的所有演员构成顶点集V，其中两位演员u和v如果共同出演过至少一部影片，那么在u和v之间连接一条边。演员之间的这种合作关系看作对等关系。按照这种方式建立的图是无向图。
将多个城市构成顶点集V，如果城市a和城市b之间有一条高速公路，则在a和b之间连接一条边。允许在两个城市之间修建多条高速公路。按照这种方式建立的图是多重图。
无向图 有向图
连通图 强连通图
连通子图 强连通子图
连通分量 强连通分量
有时候，图不仅要表示出元素之间是否存在某种关系，同时还需要表示与这一关系相关的某些信息。
例如在计算机网络对应的图中，顶点表示计算机，顶点之间的边表示计算机之间的通讯链路。实际中，为了管理计算机网络，我们需要这个图包含更多的信息，例如每条通讯链路的物理长度、成本和带宽等信息。为此，为传统图中的每条边添加相应的数据域以记录所需要的信息。
无向图 有向图
无向边 有向边（弧）
端点 弧头 弧尾
相邻的 邻接到 邻接自
度 出度 入度
连通图 强连通图
连通子图 强连通子图
连通分量 强连通分量
图的存储结构
邻接矩阵
邻接表(逆邻接表)
特点：
无向图的邻接矩阵对称，可压缩存储；有n个顶点的无向图所需存储空间为n(n+1)/2
有向图邻接矩阵不一定对称；有n个顶点的有向图所需存储空间为n²
对有向图建立逆邻接表（顶点的指向关系与邻接表恰好相反），根据逆邻接表，很容易统计出图中每个顶点的入度。
邻接矩阵 vs. 邻接链表
采用邻接矩阵还是用邻接表来存储图，要视对给定图实施的具体操作。
对边很多的图(也称稠密图), 适于用邻接矩阵存储,因占用的空间少。
对顶点多边少的图(也称稀疏图)，若用邻接矩阵存储，对应的邻接矩阵将是一个稀疏矩阵，存储利用率很低。因此，顶点多而边少的图适于用邻接表存储。
广度优先遍历
● 基本思想：
首先访问初始点顶点v0，之后依次访问与v0邻接的全部顶点w1，w2，…，wk。然后，再顺次访问与w1，w2，…，wk邻接的尚未访问的全部顶点，再从这些被访问过的顶点出发，逐个访问与它们邻接的尚未访问过的全部顶点。依此类推，直到连通图中的所有顶点全部访问完为止。
图的广度优先遍历类似于树的层次遍历，是一种分层的搜索过程，每前进一层可能访问一批顶点，不像深度优先搜索那样有时需要回溯.因此，广度优先搜索不是一个递归过程，也不需要递归算法。
为了实现逐层访问，算法中使用了一个队列，记忆还未被处理的节点，用以确定正确的访问次序。
与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组 visited [ ]，给被访问过的顶点加标记。
拓扑排序
一个任务（例如一个工程）通常可以被分解成若干个子任务，要完成整个任务就可以转化为完成所有的子任务。在某些情况下，要求一些子任务必须先于另外一些子任务被完成。
各任务之间的先后关系可以用有向图来表示。
各任务之间有序。
例1 计算机专业学生的学习就是一个任务，每一门课程的学习就是整个任务的一个子任务。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有先后关系，有的课程可以并行地学习。
拓扑排序算法基本步骤：
① 从网中选择一个入度为0的顶点且输出之。
② 从网中删除该顶点及其所有出边。
③ 执行① ② ，直至所有顶点已输出，或网中剩余顶点入度均不为0（说明网中存在回路，无法继续拓扑排序）。
注意：对于任何无回路的AOV网，其顶点均可排成拓扑序列，并且其拓扑序列未必唯一 。
假定AOV网用邻接表的形式存储。为实现拓扑排序算法，事先需好两项准备工作：
建立一个数组count[ ]，count[i]的元素值取对应顶点i的入度；
建立一个堆栈，栈中存放入度为0的顶点，每当一个顶点的入度为0，就将其压入栈。
关键路径
AOV网(Activity On Vertex):顶点表示活动或任务(Activity)，有向边表示活动（或任务）间的先后关系。
AOE网(Activity On Edges):有向边表示活动或任务(Activity) ，用边上的权值表示活动的持续时间，顶点称为事件(Event)：表示其入边的任务已完成，出边的任务可开始的状态
在AOE网络中, 有些活动顺序进行，有些活动并行进行。
从源点到各个顶点，以至从源点到汇点的有向路径可能不止一条。这些路径的长度也可能不同。
只有各条路径上所有活动都完成了，整个工程才算完成。
因此，完成整个工程所需的最短时间取决于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和。这条路径长度最长的路径就叫做关键路径(Critical Path)。
● 路径长度：指路径上的各边权值之和。
关键活动算法
求关键活动的基本步骤：
对AOE网进行拓扑排序, 按拓扑次序求出各顶点事件的最早发生时间ve ;若网中有回路终止算法;
按拓扑序列的逆序求各顶点事件的最迟发生时间vl;
根据ve和vl的值，求各活动的最早开始时间e(i)与最迟开始时间l(i)，若e(i)=l(i)，则 i 是关键活动。
最短路径问题
两顶点间可能存在多条路径
从一个指定的顶点到达另一指定顶点的路径中各边权值之和为最小的路径被称为最短路径。
城市交通导航
计算机网络信息传送问题
单源最短路径: 给定顶点到其它所有顶点的最短路径问题
无权最短路径
正权最短路径
多源最短路径：每对顶点之间的最短路径问题
无权最短路径问题
源点到各顶点的路径所经历的边的数目就是路径的长度
相对于源点由近及远依次求各顶点的最短路径
正权最短路径问题
问题：给定一个带权图 G 与源点 v，求从 v 到 G 中其它顶点的最短路径，限定各边的权值为正实数.
Dijkstra算法
基本思想：将图中所有顶点分成两个集合，第一个集合S包括已确定最短路径的顶点，第二个集合T包括尚未确定最短路径的顶点。按照最短路径长度递增的顺序逐个把第二组的顶点加到第一组中去，直至从源点出发可以到达的所有顶点都包括到第一组中。
定理 Dijkstra算法可以按照非递减次序依次得到各顶点的最小路径长度。
单源最短路径: 给定顶点到其它所有顶点的最短路径问题
无权最短路径
正权最短路径
多源最短路径：每对顶点之间的最短路径问题
最小支撑树
1、基本概念
2、生成最小支撑树算法
Prim算法
Kruskal算法
若要在n个顶点之间建立连通图，至少要有n-1条边来连接这n个顶点，将这n-1条边上的权值之和定义为连通图的代价。
对于一个无向加权连通图N=(V,E,C)（C表示该图为权图），其顶点个数为n，图中边的个数为e ，我们可以从它的e条边中选出n-1条边，使之满足
（1）这n-1条边和图的n个顶点构成一个连通图。
（2）该连通图的代价是所有满足条件(1)的连通图的代价的最小值。
这样的连通图被称为图N的最小支撑树。
最小支撑树的性质
最小支撑树(MST)中无回路
若MST 的边集中有回路，显然可通过去掉回路中某条边而得到代价更小的MST
MST是一棵有n -1条边的树
最小
满足最小支撑树要求的边集所构成的树支撑起了所有的顶点(即把它们联接起来了)
此边集的代价最小
最小支撑树的应用
在 n 个城市间建立造价最低的通讯网络