?????????复习王道丛书的时候，图这章差不多花了四天把，主要题目有些难搞，做题目花了好长时间，废话就不说了。
1.图需要记住的一些概念
? ? ? ? 图的有些概念题是真的绕，图的基本概念的话就不多讲了，就是顶点集和边集构成的图；值得去记忆的是一些特殊的图，有向图（有箭头，度=出度+入度），无向图（直接连在顶点上的那种）；然后还有简单图（不存在重复边和指向自己的边）；完全图（任意两个顶点都存在边，因此边数也是n（n-1）/2）；子图（注意不是说给你一个顶点集和边集就可以组成一个子图）；然后就是连通图，连通图就是任意两个顶点之间都可以到达，否则就是非连通图，且连通图最少会有n-1条边，然后极大连通子图称为连通分量，类比极大无关组。强连通图就是相互都有路径（有向图中讨论），强连通分量和上面差不多的意思，后面的出度入读，路径就不说了，很好理解的都是。
然后就是一些错题：
【1】一个有28条边的非连通无向图至少有多少个顶点？
【2】G有23条边，度为4的顶点有5个，度为3的顶点有4个，其余都是度为2的顶点，G最多有多少个顶点？
【3】具有n个顶点的图是一个环，则它有多少棵生成树？
【4】一个具有n个顶点，e条边的无向图是一个森林，则森林必有多少棵树？
2.图的存储操作
? ? ? ? 关于图的存储的话，我们需要知道一些常用的存储方法就ok了，第一个是邻接矩阵法，这种方法感觉经常拿来考，就是说给你一个图吧，比如A->B->C->D，怎样把它放到矩阵里边儿？其实，只需要构建一个二维数组就行了：（适合稠密图）
? ? ? ? 然后就是邻接表法，邻接表利用了顺序和链式存储，给定一个顶点它可以快速找出邻边，但是如果你要求入度则要访问整个表了，邻接表也多用来存储稀疏图?
? ? ? ? ?剩下的两种，一个是十字链表法和邻接多重表，前者只存有向图，后者为无向图的链式存储结构
?错题：
【1】含有n个顶点和e条边的无向邻接矩阵中的零元素个数为？
【2】邻接表存储所用的空间与什么有关？
【3】如果邻接表有奇数个边表结点，则？
【4】n个顶点的无向图的邻接表最多有多少个边表结点？
3.图的遍历
? ? ? ? 图的遍历的话搞懂BFS和DFS就ok了，弄懂他们的时间复杂度，广度优先生成树和深度优先生成树，首先BFS（广度优先遍历，类似于树的层序遍历）的话，它的遍历过程就是，比如说给你一个图
?就是这个图，假设从1开始，先访问1，再访问与1相邻的两个结点2和8，再取出2，访问与2相邻的两个元素直，再取8访问与8相邻的两个元素，以此类推。BFS需要借助一个辅助队列Q，n个顶点均要入队一次，然后就是关于BFS的时间复杂度的问题了，如果是邻接表存储的话时间复杂度为O（V+E），采用邻接矩阵的话则为O（V^2）;然后是广度优先生成树，，广度遍历的过程我们可以得到一个广度优先生成树，注意一个给定邻接矩阵所表示是唯一的，其广度优先生成树也是为一个，而邻接表就不一样了，它的广度优先生成树并不唯一。
? ? ? ? 然后就是DFS了，DFS类似于树里面的先序遍历，策略是较为深的访问一个图，就拿上一个图来说的话，不像BFS访问两个一样，DFS会访问于下一个结点相邻的一个结点，直到都访问过了再出来。DFS需要借助递归工作栈来实现。然后它的空间复杂度为O（V）总时间复杂度为O（V+E）,深度优先树森林和广度优先差不多，这里不赘述。
? ? ? ? 错题：
【1】使用DFS算法递归遍历一个无环有向图，退出递归时输出相应的顶点，则这样得到的是什么序列？
【2】广度优先生成树的高比深度优先生成树的高要？
【3】无向图G{V,E}其中V={a,b,c,d,e,f},E={(a,b).(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}进行深度优先遍历的话可以得到哪些序列？
4.图的应用
? ? ? ? 图的应用这一节涉及到了好多的算法概念之类的，需要好好去回味以下，特便是那几个算法（普利姆,迪杰斯特拉，克鲁斯卡尔，弗洛伊德）这几个算法好重要，还有拓扑排序的应用概念，还有一个就是关键路径的寻找和怎么去算最早开始时间和最迟开始时间。因为太多了还是用题目来回顾吧，但是基本的一些还是写一下吧。
? ? ? ? 4.1 最小生成树
? ? ? ? ? ? ? ? 所谓最小生成树，一个带权无向图中代价最小的那颗生成树，然后需要注意一点，最小生成树的树形并不唯一，但是代价唯一，最小生成树的边数为顶点数减1 。
? ? ? ? 4.2 普利姆算法
? ? ? ? ? ? ? ? 普利姆算法从一个顶点出发后，扫描与之相连的边，然后找到权值最小的边，加入树T中，以此类推，直到所有的顶点都并入T中，里面必然有n-1条边，具体看题目吧。(适用于边稠密的图)
? ? ? ? 4.3克鲁斯卡尔算法
? ? ? ? ? ? ? ? 克鲁斯卡尔算法和普利姆其实是反正普利姆来的，前者是找点，后者是找边，不断选择未被选取过且权值最小的边，直到所有的顶点都在T里面。（适用于边稀疏而顶点较多的图）
? ? ? ? 4.4迪杰斯特拉算法
? ? ? ? ? ? ? ? 迪杰斯特拉算法其实就是一种贪心算法，怎么说呢，其实用语言不太好描绘，直接上一个王道讲解的一个图吧来搭配理解，反正就是用小的取代大的，然后把相应的顶点加入到最短序列数组里面，做题的时候就按下面的思路来就行了；图中第一趟从1开始，先把1加入集合里面，然后可以从1到2和5两个点，但是到5的距离比到2短，所以选择5，并把5加入集合，集合现在有{1，5}，然后第二趟，刚刚加入的点不要再次写（遍历），其它点的值照写到下一趟，就如下图第二趟那一列所示，又因为第二趟到5的时候，和5相邻的有2，4，6三个点，从5到4的距离为11，到6的距离为11，但是到2因为是照写过来的所以直接比较，发现从1到2的综合最小，所以把2加入集合，集合变为{1，5，2}，后面以此类推~
? ? ? ? 4.5佛洛依德算法
? ? ? ? ? ? ? ? 弗洛伊德算法好似一种动态规划的算法，就是先看两个点加一个中转点后面的路径长度和之前比较的话哪一个更短，每次新增一个中转点递推考虑，中转点的更新：
（A[0][1]>A[0][2]+A[2][1] 以V2中转）
? ? ? ? 4.6有向无环图的表达式
? ? ? ? ? ? ? ? 这个内容主要就是给你一段运算符和数，让你把它转成图，算出虽短要多少条边，或是顶点，这里王道给出了一种很方便的方法求解，如图：
??????????????????????????
? ? ? ? 4.7拓扑排序
? ? ? ? ? ? ? ? 拓扑排序其实挺简单的，只需要记住他是一个有向无环图，然后拓扑排序的过程就是寻找入度为0的顶点，删除那个结点和它的边，依次进行，直到最后一个结点被弹出
? ? ? ? 4.8关键路径
? ? ? ? ? ? ? ? 关键路径的话你要知道什么是关键路径，关键路径就是具有最大路径长度的路径，然后需要知道最早发生时间和最迟开始时间，用一个例子来理解：
?错题：
【1】一个有向图具有有序的拓扑序列，它的邻接矩阵必定是？