Chapter 7 Diagram
第 7 章 图
图（Graph）摒弃了以往的一对一、一对多关系，图的任意两个数据元素之间都可能相关。
图是由顶点的有穷非空集合和顶点之间边的集合组成的，通常表示为G（V，E），其中G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
图中数据元素：称为顶点（Vertex）
不同于空表和空树，图结构中，不允许没有顶点
图中，任意两个顶点之间都可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空的
其他图相关的定义：
无向边（Edge），若任意两个顶点之间的边都是无向边，称为无向图（undirected graphs）
有向边/弧（Arc），箭头指向为弧头（Head），箭头尾为弧尾（Tail），同理，可以形成有向图（directed graphs）。可以用有序偶来表示<A，D>（连接顶点A到D的有向边）
无向边用小括号 ( ) 表示，有向边用尖括号<>表示
简单图：不存在顶点到其自身的边、同一条边不重复出现
无向图中，任意两个顶点都存在边，称为无向完全图：n个顶点有[n*(n-1)]/2条边
有向图中，任意两个顶点之间都存在方向相反的两条弧，称为有向完全图：n个顶点有n*(n-1)条边
有很少条边或弧的称为稀疏图，反之称为稠密图。（模糊概念、相对而言）
与图的边或弧相关的数叫做权（Weight），带权的图通常称为网（Network）
子图（Subgraph）：部分顶点，但保留了其中的关系（边）
邻接点（Adjacent）、依附（incident）、顶点的度（Degree）
入度（InDegree）、出度（OutDegree）、路径（Path）：路径的长度是路径上的边或弧的数目
回路/环（Cycle），序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路称为简单回路或简单环。
连通图（Connected Graph）：任意两个顶点之间都有路径
无向图中的极大连通子图称为连通分量、有向图中称为强连通分量
无向图中连通且n个顶点n－1条边叫生成树，有向图中一顶点入度为0其余顶点入度为1的叫有向树。一个有向图由若干棵有向树构成生成森林
图的存储结构
由于其物理关系逻辑复杂，不能用简单的顺序存储结构表示，同时对于多重链表方式，由于度数相差大，造成存储单元浪费
邻接矩阵
邻接矩阵（Adjacency Matrix）存储方式是用两个数组来表示图。一个一位数组存储图中顶点信息，一个二维数组（称为邻接矩阵）存储图中的边或弧的信息
0
1
2
0
0
7
2
1
8
0
∞
2
2
3
0
如（0，1）表示顶点0到1的权值为7（有向），1到0为8，其中，没有连接的线标为∞，自己对自己的权值（对角线）为0；
对于无向图，即
0
1
2
0
0
7
2
1
7
0
3
2
2
3
0
矩阵变为对称矩阵（计算机理解为有向图的正向和反向的权值相等）
无向图的边数组就是对称矩阵
有向图的权值，用边数组中元素值代替，∞表示不存在（而不是0）
时间复杂度：O(n+n2+e)、空间复杂度：O(n2 )
邻接表
数组与链表相结合的存储方法称为邻接表（Adjacency List）：关心顶点的出度
逆邻接表：关心入度
十字链表
将邻接表和逆邻接表结合，同时关注入度和出度问题：十字链表（Orthogonal List）
顶点表结点结构
data
firstin
firstout
数据
入边表头指针：指向该顶点的入边表中第一个结点
出边表头指针：指向该顶点的出边表中第一个结点
边表结点结构
tailvex
headvex
headlink
taillink
弧起点在顶点表中的下标
弧终点在顶点表中的下标
入边表指针域：指向终点相同的一条边
边表指针域：指向起点相同的下一条边
如果是网，可以再增加一栏weight域存储权值
邻接多重表
前面关注了有向图的存储结构，下面关注无向图
定义边表结点结构
ivex
ilink
jvex
jlink
与某条边依附的顶点之一，在顶点表中的下标
指向依附顶点ivex的下一条边
与某条边依附的顶点之二，在顶点表中的下标
指向依附顶点jvex的下一条边
边集数组
边集数组由两个一维数组构成。一个存储顶点信息；另一个是存储边的信息，这个边数组每个数据元素由一条边的起点下标（begin）、终点下标（end）和权（weight）组成
定义的边数组结构
begin
end
weight
存储起点下标
存储终点下标
存储权值
图的遍历
希望从图的某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次，这一过程就叫做图的遍历（Traversing Graph）
深度优先遍历
又称深度优先搜索（Depth First Search，DFS）
从图中某个顶点
出发，访问此顶点，然后从v的未被访问的邻接点出发深度优先遍历图，直至图中所有和v有路径相通的顶点都被访问到。
若图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
void DFS(Graph G, int v)
{
visuted[v] = TURE;
VisitFun(v);
for(w = FirstAdjVex...)
if(!vistit) DFS...
}算法分析：
使用邻接矩阵的方式算法复杂度为
类似树的前序遍历
广度优先遍历
又称广度优先搜索（Breadth First Search，BFS）
首先访问指定顶点，并将该顶点作为当前顶点。
利用队列进行逻辑关系维护
void BFSTravers(AlGraph G)// 对图做广度优先遍历
{ for() visited[v] = FALSE;// 初始化标志数组
// 置空队列
// 若v未访问
// 访问，修改标志位，入队
// 若队列非空
// 出队
// 从第一邻接点起
// 访问第w个节点
// 第w个顶点入队
}算法分析：
图中每个顶点至多入队一次，因此外循环次数为 n
邻接表方式存储 图G，复杂度同为
类似树的层序遍历
最小生成树
我们把构造连通网的最小代价生成树成为最小生成树（Minimum Cost Spanning Tree）
在无向图中求一棵树（n-1条边，无环，连通所有点）而且这棵树的边权和最小
最小生成树的 MST 性质
普里姆算法（Prim）
俗称加点法：
从任何图上一个点开始
加上连接这个点权重最小的点
重复第 2 步（最小权重可能一样，所以最小生成树可能不唯一）
然后找连接已有的点权重最小的点（此时已有 3 个点）
重复第 5 步
直到所有的点都加进树中，形成最小生成树
关注点，不太关注边（适合稠密图）
时间复杂度为
克鲁斯卡尔（Kruskal）算法
俗称加边法：
先取出所有的点
加上权值最小的边
重复第 2 步
重复第 2 步，但此时要注意，现在加的边的顶点两端不能连通（不能是连通分量，并且最小权重可能一样，所以最小生成树可能不唯一）
重复第 5 步
关注边，不太关注点（适合稀疏图）
时间复杂度为O(eloge)
无向图的最小生成树是不唯一的，但是加权和是唯一的
最短路径（工程应用）
对于网图来说，最短路径，是指两顶点之间经过的边上权值之和最少的路径，并且我们称路径上的第一个顶点是源点，最后一个顶点是终点
迪杰斯特拉（Dijkstra）算法
按照路径长度递增的次序产生最短路径的算法。
弗洛伊德（Floyd）算法
准备两个二维矩阵
D和Path
D：顶点到顶点的最短路径权值和
Path：对应顶点的最短路径的前驱矩阵，存储路径
最终要求解的是顶点之间的最短路径（打破两点之间直连最短的思想）
从-1初始化开始，到以 0 为中间点...到以n为中间点的过程
如果你面临需要求所有顶点之所有顶点的最短路径问题时，弗洛伊德算法应该是不错的选择
拓扑排序（有向无环图！！！）（工程应用）
拓扑排序介绍
在一个表示工程的有向无环图中，用顶点表示活动，用弧表示活动之间的优先关系，这样的有向图为顶点表示活动的网，我们称为AOV网（Actvity On Vertex Network）
图中的顶点进行排序v1，v2...，vn，满足从第i项和第j项有一条路径，则在顶点序列中顶点vi必在vj之前，这样的顶点序列称为拓扑序列
拓扑排序就是对一个有向图构造拓扑序列的过程，拓扑排序可能不唯一
拓扑排序算法
可以有效分析出一个有向图是否有环（会卡住......），如果不存在，可以分析出它的拓扑序列
关键路径
在一个表示工程的带权有向图中，用顶点表示事件，用有向边表示活动，用边上的权值表示活动的持续时间，这种有向图的边表示活动的网，称为AOE网（Acitivity On Edge Network）
路径上各个活动所持续的时间之和称为路径长度，从源点到汇点具有最大长度的路径叫关键路径，在关键路径上的活动叫关键活动
关键路径算法
几个参数
事件的最早发生时间（earliest time of vertex）
事件的最晚发生时间（latest time of vertex）
活动的最早开工时间（earliest time of edge）
活动的最晚开工时间（latest time of edge）
由1，2可以得出3，4。
利用关键路径算法可以得到最短完成工程工期以及其关键活动有哪些
Last updated