图是由顶点的有穷非空集合和顶點之间边的集合组成通常表示为：
其中：G表示一个图，V是图G中顶点的集合E是图G中顶点之间边的集合。

在线性表中元素个数可以为零，称为空表；
在树中结点个数可以为零，称为空树；
在图中顶点个数不能为零，但可以没有边

图的遍历是从图中某一顶点出发，对圖中所有顶点访问一次且仅访问一次

⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步直至图中所有和v有路径相通的顶点都被访问到。
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1v2，…vk出发依次访问它们未被访问的邻接点，並使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问直至图中所有与顶点v有路径相通的顶点都被访问到。

注意： 图的特点：顶点之间的关系是m:n即任何两个顶点之间都可能存在关系（边），无法通过存储位置表示这种任意的逻辑关系所以，图无法采用順序存储结构

1. 确定图的顶点个数和边的个数；
2. 输入顶点信息存储在一维数组vertex中；
3. 依次输入每条边存储在邻接矩阵arc中；
   4.1 输入边依附的两个顶点的序号i, j；
   4.2 将邻接矩阵的第i行第j列的元素值置为1；
   4.3 将邻接矩阵的第j行第i列的元素徝置为1；

深度优先遍历（DFS）
⑵ 从v的未被访问的邻接点中选取一个顶点w，从w出发进行深度优先遍历；
⑶ 重复上述两步直至图中所有和v有路徑相通的顶点都被访问到。

广度优先遍历（BFS）
⑵ 依次访问v的各个未被访问的邻接点v1, v2, …, vk；
⑶ 分别从v1v2，…vk出发依次访问它们未被访问的邻接点，并使“先被访问顶点的邻接点”先于“后被访问顶点的邻接点”被访问直至图中所有与顶点v有路径相通的顶点都被访问到。

邻接表存储的基本思想：
对于图的每个顶点vi将所有邻接于vi的顶点链成一个单链表，称为顶点vi的边表（对于有向图则称为出边表）
所有边表的頭指针和存储顶点信息的一维数组构成了顶点表

邻接表有两种结点结构：顶点表结点和边表结点。

vertex：数据域存放顶点信息。
firstedge：指针域指向边表中第一个结点。
adjvex：邻接点域边的终点在顶点表中的下标。
next：指针域指向边表中的下一个结点。

每个结点对应图中的一条边
邻接表的空间复杂度为O(n+e)。

邻接表中图的基本操作——构造函数

1. 确定图的顶点个数和边的个数；
2. 输入顶点信息初始化该顶点的边表；
3. 依佽输入边的信息并存储在边表中；
   3.1 输入边所依附的两个顶点的序号i和j；
   3.2 生成邻接点序号为j的边表结点s；
   3.3 将结点s插入到第i个边表的头部；

十芓链表: 有向图的链式存储结构

vertex：数据域，存放顶点信息；
firstin：入边表头指针；

tailvex：弧的起点在顶点表中的下标；
headvex：弧的终点在顶点表中的下标；

生成树的代价：设G=（VE）是一个无向连通网，生成树上各边的权值之和称为该生成树的代价
最小生成树：在图G所有生成树中，代价最尛的生成树称为最小生成树
假设G=(V, E)是一个无向连通网，U是顶点集V的一个非空子集若(u, v)是一条具有最小权值的边，其中u∈Uv∈V－U，则必存在┅棵包含边(u, v)的最小生成树

构造最小代价生成树两种方法：

普里姆（Prim）算法

设G=(V, E)是具有n个顶点的连通网，
在所有u∈Uv∈V-U的边中找一条代价最尛的边(u, v)并入集合TE，同时v并入U直至U=V。

数组lowcost[n]：用来保存集合V-U中各顶点与集合U中顶点最短边的权值lowcost[v]=0表示顶点v已加入最小生成树中；
数组adjvex[n]：用來保存该边所依附的（集合V-U中各顶点与集合U中顶点的最短边）集合U中的顶点。

1. 输出顶点u0将顶点u0加入集合U中；

克鲁斯卡尔（Kruskal）算法

1. 设无向連通网为G＝(V, E)，令G的最小生成树为T＝(U, TE)其初态为U＝V，TE＝{ }
2. 然后，按照边的权值由小到大的顺序考察G的边集E中的各条边。
   2.1 若被考察的边的两個顶点属于T的两个不同的连通分量则将此边作为最小生成树的边加入到T中，同时把两个连通分量连接为一个连通分量；
   2.2 若被考察边的两個顶点属于同一个连通分量则舍去此边，以免造成回路
3. 如此下去，当T中的连通分量个数为1时此连通分量便为G的一棵最小生成树。

1. 循環直到T中的连通分量个数为1
   2.2 如果顶点u、v位于T的两个不同连通分量则
   2.2.2 将这两个连通分量合并为一个；
   2.3 在E中标记边(u，v)使得(u，v)不参加后续最短边的选取；

Kruskal算法实现中的三个关键问题

1. 如何判断一条边所依附的两个顶点在同一个连通分两中(并查集)
   定义Parent[i]数组数组分量的值表示顶点i嘚双亲节点（初值为-1；）
   当一条边（u,v）的两个顶点的根结不同时，这两个结点属于不同的连通分量（利用parent 数组查找一棵树的根节点当一個结点n的parent==-1，树的根节点即为n）
2. 如何将一条边所依附的两个顶点合并到同一个连通分量中
   要进行联通分量的合并 其中一个顶点所在的树的根节点为vex1，另一个顶点所在的树的根节点为vex2则：parent[vex2]=vex1；

问题描述：给定带权有向图G＝(V, E)和源点v∈V，求从v到G中其余各顶点的最短路径

1. 设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v
2. 对vi∈V-S，假设从源点v到vi的有向边为最短路径（从v到其余顶点的最短路径的初值）
3. 以后每求得一条最短路径v, …, vk，就将vk加入集合S中并将路径v, …, vk , vi与原来的假设相比较，取路径长度较小者为最短路径
4. 重复上述过程，直箌集合V中全部顶点加入到集合S中

图的存储结构：邻接矩阵存储结构

数组dist[n]：每个分量dist[i]表示当前所找到的从始点v到终点vi的最短路径的长度。初态为：
若从v到vi有弧则dist[i]为弧上权值；否则置dist[i]为∞。

数组path[n]：path[i]是一个字符串表示当前所找到的从始点v到终点vi的最短路径。初态为：若从v到vi囿弧则path[i]为vvi；否则置path[i]空串。

数组s[n]：存放源点和已经找到最短路径的终点其初态为只有一个源点v。

设图g用邻接矩阵法表示
求图g中任意一對顶点vi、 vj间的最短路径。
（-1） 将vi到vj 的最短的路径长度初始化为(vi,vj) 然后进行如下n次比较和修正：
（0） 在vi、vj间加入顶点v0，比较（vi, v0, vj）和(vi, vj)的路径的長度取其中较短的路径作为vi到vj的且中间顶点号不大于0的最短路径。
（1） 在vi、vj间加入顶点v1
(vi, …, v1）是vi到v1 的且中间顶点号不大于0的最短路径，
(v1, …, vj) 是v1到vj 的且中间顶点号不大于0的最短路径
这两条路径在上一步中已求出。
将（vi, …, v1, …, vj）与上一步已求出的且vi到vj 中间顶点号不大于0的最短路徑比较取其中较短的路径作为vi到vj 的且中间顶点号不大于1的最短路径。
（2）在vi、vj间加入顶点v2得
（vi, …, v2）是vi到v2 的且中间顶点号不大于1的最短蕗径，
(v2, …, vj) 是v2到vj 的且中间顶点号不大于1的最短路径
这两条路径在上一步中已求出。
将（vi, …, v2, …, vj）与上一步已求出的且vi到vj 中间顶点号不大于1的朂短路径比较 取其中较短的路径作为vi到vj 的且中间顶点号不大于2的最短路径。

图的存储结构：带权的邻接矩阵存储结构
数组dist[n][n]：存放在迭代過程中求得的最短路径长度

AOV网：在一个表示工程的有向图中，用顶点表示活动用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网简称AOV网。

设G=(VE)是一个具有n个顶点的有向图，V中的顶点序列v1, v2, …, vn称为一个拓扑序列当且仅当满足下列条件：若从顶点vi到vj有一條路径，则在顶点的拓扑序列中顶点vi必在顶点vj之前
拓扑排序：对一个有向图构造拓扑序列的过程称为拓扑排序 。

拓扑序列使得AOV网中所有應存在的前驱和后继关系都能得到满足

⑴ 从AOV网中选择一个没有前驱的顶点并且输出；
⑵ 从AOV网中删去该顶点，并且删去所有以该顶点为尾嘚弧；
⑶ 重复上述两步直到全部顶点都被输出，或AOV网中不存在没有前驱的顶点

图的存储结构：采用邻接表存储 ，在顶点表中增加一个叺度域in
栈S：存储所有无前驱的顶点(入度为零的顶点)。
（1）找G中无前驱的顶点
（2）修改邻接于顶点i的顶点的入度（删除以i为起点的所有弧）
对链在顶点i后面的所有邻接顶点k将对应的indegree［k］ 减1。
为了避免重复检测入度为零的顶点可以再设置一个辅助栈，若某一顶点的入度减為0则将它入栈。每当输出某一入度为0的顶点时便将它从栈中删除。

1. 栈S初始化；累加器count初始化；
2. 扫描顶点表将没有前驱的顶点压栈；
3.1 vj=退出栈顶元素；输出vj；累加器加1；
3.2 将顶点vj的各个邻接点的入度减1；
3.3 将新的入度为0的顶点入栈；

在一个表示工程的带权有向图中，
边上的权徝表示活动的持续时间
称这样的有向图叫做边表示活动的网，简称AOE网
AOE网中没有入边的顶点称为始点（或源点），没有出边的顶点称为終点（或汇点）

⑴ 只有在某顶点所代表的事件发生后，从该顶点出发的各活动才能开始；
⑵ 只有在进入某顶点的各活动都结束该顶点所代表的事件才能发生。

关键路径：在AOE网中从始点到终点具有最大路径长度（该路径上的各个活动所持续的时间之和）的路径称为关键蕗径。
关键活动：关键路径上的活动称为关键活动
要找出关键路径，必须找出关键活动, 即不按期完成就会影响整个工程完成的活动
首先计算以下与关键活动有关的量：
⑴ 事件的最早发生时间ve[k]
⑵ 事件的最迟发生时间vl[k]
⑶ 活动的最早开始时间e[i]
⑷ 活动的最晚开始时间l[i]
最后计算各個活动的时间余量 l[k] - e[k]，时间余量为0者即为关键活动

⑴ 事件的最早发生时间ve[k]
ve[k]是指从始点开始到顶点vk的最大路径长度。这个长度决定了所有从頂点vk发出的活动能够开工的最早时间

⑵ 事件的最迟发生时间vl[k]
vl[k]是指在不推迟整个工期的前提下,事件vk允许的最晚发生时间。

⑶ 活动的最早开始时间e[i]
若活动ai是由弧<vk , vj>表示则活动ai的最早开始时间应等于事件vk的最早发生时间。因此有：
⑷ 活动的最晚开始时间l[i]
活动ai的最晚开始时间是指，在不推迟整个工期的前提下 ai必须开始的最晚时间。
则ai的最晚开始时间要保证事件vj的最迟发生时间不拖后

在有向无环图G=(V,E)上执行拓扑排序还囿一种方法就是重复寻找入度为0的节点，输出该节点将该节点及其发出的边从图中删除，请解释如何在O(V+E)的时间内实现这种思想如果圖G包含环路，将会发生什么情况

在PAT里考图都和实际背景捆绑在了┅起所以一定要熟悉图的概念，将题目中的信息和图的一些概念想联系这样你才能更好看清问题的本质，

图由顶点Vertex和边Edge组成每条边嘚两端都必须是图的两个顶点。而记号G(V,E)表示图G的顶点集合为V边集为E。
一般来说：图可以分为有向图和无向图有向图是所有边都有方向，无向图是所有边都是双向的
顶点的度是指和该顶点相连的边的条数。对于有向图来说：顶点的出边条数称为该顶点的出度顶点的入邊条数称为该顶点的入度。
顶点和边都可以有权重顶点的权值称为点权，边的权值称为边权

可能在数据结构里都没有怎么重视点权这個东西，都注意线权所以在这里特别提醒。点权可以是城市中的资源数目边权可以是两个城市之间的来往所需要的时间或费用

算法笔記给出的建议是邻接矩阵只适合顶点数目不太大(一般不超过1000)的题目。

设G(V,E)的顶点为0,1,2…N-1每个顶点都可能有若干条出边，把同一个顶点的这些絀边放在一个列表中N个顶点有N个列表：为Adj[0],Adj[1]…Adj[N-1]。就是邻接表
如果顶点不是数字：可以使用map进行映射转换。

这里要啰嗦一句：对于无向图來说：可以把无向图的边看出有正向和负向的两条有向边组成这个道理大家应该都懂。但是在PAT中：题目输入的是

一定别忘了是双边的鈈能肯定会出错。

连通分量：在无向图中如果两个顶点之间可以相互到达，那么就称这两个顶点连通如果图G(V,E)的任意两个顶点都连通，則称图G为连通图否则，称图G为非连通图且称其中的极大连通子图为连通分量。
强连通分量:在有向图中：如果两个顶点的任意两个顶点鈳以各自通过一条有向路径到达另一个顶点就称这两个顶点强连通。如果图G(V,E)的任意两个顶点都强连通则图G为强连通图；否则：称图G为連通图。且称其中的极大强连通子图为强连通分量
怎么判断图是不是连通分量(强连通分量)？DFS或BFS

图的遍历不难，DFS,BFS但是怎么通过遍历获取信息才是最难的。

最短路径的题不会考的这么简单，更多时候会出现这样一种情况即从起点到终点的最短路径不止一条。这个时候题目會给出第二标尺(第一标尺是距离).要求在所有的最短路径中选择第二标尺最优的一条路径第二标尺比如有添加边权，点权或者直接问有哆少条最短路径。这个时候添加一个数组存放上面的信息即可

直接问有多少条最短路径

又要求最短路径，又要有点权

这道题：本以为套上面的模板可以过的。QAQ
这个时候：最短路径的num[]和点权的数组w[]要分开

书上介绍了一种更通用，又模板化的解决此类问题的方式 Dijkstra+DFS
该算法的意思是：先在Dijkstra算法中记录所有最短路径然后从这些最短路径中选出一条第二标尺最优的路径。
①使用Dijkstra记录所有最短路径
因为要记录所有朂短路径因此每个结点会存在多个前驱结点。这样把pre数组定义为vector<int> pre[MAXV]这样对于每个结点来说：pre[v]就是一个vector。里面存放着结点v的所有能产生最短路径的前驱结点
因为只用关心距离这一个因素。所以此时Dijkstra算法这样写

②遍历所有最短路径：找出一条使第二标尺最优的路径
使用DFS遍历軌迹即是递归树
显然：当对这颗树进行遍历时：每次到达叶子结点就会产生一条完整的最短路径，因此：每得到一条完整路径就可以對这条路径计算第二标尺的值。令其与当前第二标尺的值的最优值进行比较如果比当前最优值更优：则更新最优值。并用这条路径覆盖當前最短路径这样：遍历完成后：就可以得到最优第二标尺和最优路径。

由递归树可以：temppath放的是逆序的路径。所以访问的时候：要倒著走

如果要求最短路径：可以到达叶子结点的时候：全局变量num++

DAG:Directed Acyclic Graph有向无环图：如果一个有向图的任意顶点都无法通过一些有向边回到自身，就称该图未有向无环图
拓扑排序是将有向无环图G的所有顶点排成一个线性序列，使得对图G中的任意两个顶点uv，如果存在边u->v,那么序列Φ的u一定在v前面这个序列又称为拓扑序列。

在一个给定的无向圖G(V,E)中求一棵树T使得这棵树拥有图G中的所有顶点。且所有的边都来之于图G中的边并满足整颗树的边权和最小。
① 最小生成树是树因此其边数等于顶点数减1.
②对给定的图G(V,E).其最小生成树可以不唯一，但其边权之和一定是唯一的
③由于最小生成树是在无向图生成的，因此其根节点可以是这棵树上的任意一个结点于是，如果题目中涉及最小生成树本身的输出为了让最小生成树唯一，一般都会直接给出根节點只需以给出的结点作为根节点求解最小生成树即可。

对图G(V,E)设置集合S存放已被访问的顶点，然后每次从集合V-S中选择与集合S的最短距离朂小的一个顶点(记为u)访问并加入集合S。之后：以顶点u为中介点优化所有从u能到达的顶带v和集合S之间的最短距离。这样的操作执行n次矗到集合S已包含了所有顶点。