3、图的遍历
遍历的定义： 从已给的连通图中某个顶点出发，沿着一些边访问遍图中所有的顶点，且使得每个顶点仅被访问一次，就叫做图的遍历，它是图的基本运算。图遍历的实质是：找每个顶点的邻接点的过程。
图的特点： 图中可能存在回路，且图的任一顶点都可能与其他顶点相连通，在访问完某个顶点之后，可能会沿着某些边右回到曾经访问过的顶点。可以设置一个辅助数组visited[n]，记录已经被访问过的顶点，初始状态均置为0，若顶点i被访问过了，则visited[i]置为1，从而放置顶点的多次访问。
3.1 深度优先搜索-DFS
在访问图中的某个起始顶点v之后，由v出发，访问它的任意一个邻接顶点 w1；
再从 w1出发，访问与 w1邻接但是还没有被访问过的顶点 w2；
然后再从 w2出发，进行类似的访问… ;
如此进行下去，直到到达所有的邻接顶点都被访问过的u为止；
接着退回一步，退到前一次刚访问过的顶点，看是否还有其他没有被访问的邻接顶点；
如果有，则访问此顶点，之后再从此顶点出发，进行与之前类似的访问；
如果没有，则再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。
连通图的深度优先遍历类似于树的先根遍历。
采用邻接矩阵表示图的深度优先搜索遍历的实现如下所示：
void DFS(AMGraph &G, int v) { cout << v << endl; visited[v] = true; //visited为辅助记录节点是否访问的向量 for(int i = 0; i < G.vexNum; ++i) { if(G.arcs[v][i]!=0 && !visited[i]) DFS(G, i); } }
用邻接矩阵来表示图，遍历图中每个点点都要从头扫描该顶点所在的行，时间复杂度为 O(n^2)
用邻接表来表示图，虽然有2e个表结点，但只需要扫描e个结点即可以完成遍历，加上访问n个头结点的时间，时间复杂度为 O(n+e)
所以稠密图适合在邻接矩阵上进行深度遍历；稀疏图适合在邻接表上进行深度遍历。
非连通图的遍历：首先从图中任意选择一个节点进行DFS，当DFS结束之后，若visited还有没有访问的节点，则再从图中任意选择一个节点进行DFS；重复上述过程，直到visited中所有的节点均被访问过。
3.2 广度优先搜索-BFS
从图的某个结点出发，首先依次访问该结点的所有邻接顶点v1,v2,...,vm；
再按照这些顶点被访问的先后顺序依次访问与它们相邻接的所有未被访问的顶点；
重复上述过程，直到所有顶点均被访问了
借助队列实现图的广度优先遍历：
void BFS(Graph &G, int v) { cout << v; visited[v]=true; queue<int> Q; Q.push(v); while(!Q.empty()) { int top = Q.top(); Q.pop(); for(int w = FistAdjVex(G,top); w>=0; w=NextAdjVex(G,top,w)) { if(!visited[w]) { cout << w<<endl; visited[w] = true; Q.push(w); } } } }
如果使用邻接矩阵，则对于BFS每一个被访问到的顶点，都要循环检测矩阵中的一行n个元素，总的时间复杂度为 O(n2)。和深度优先遍历相同，使用邻接表的时间复杂度为 O(n+e)
DFS和BFS的空间复杂度相同，都是 O(n)，DFS借助了栈(递归借助系统中的栈)，BFS借助了队列。
4、图的应用
4.1 生成树
生成树： 所有顶点均由边连接在一起，但不存在回路的图。
一个图中可以有许多棵不同的生成树；
所有生成树具有以下共同特点：
生成树的顶点个数与图的顶点个数相同；
生成树是图的极小连通子图，去掉一条边则非连通；
· 一个有n个顶点的连通图的生成树有n-1条边；
· 在生成树中再加一条边必然形成回路。
· 生成树中任意两个顶点之间的路径唯一
含有n个顶点n-1条边的图不一定是生成树
设图 G=(V,E)是个连通图，当从图中任意一个顶点出发遍历图G时，将边集合E(G)分成两个集合 T ( G ) )和 B ( G )其中， T(G)是遍历图时经过的边的集合， B(G)是遍历图时未经过的边的集合。显然， G1(V,T)是图G的极小连通子图，即子图 G1是图G的生成树。
最小生成树：给定一个无向网络，在该网的所有生成树中，使得各边权值之和最小的那棵生成树称为该网的最小生成树，也叫最小代价生成树。
MST性质：设N=(V,E)是一个连通网， U是顶点集V的一个非空子集。若边 (U,V)是一条具有最小权值的边，其中 u∈U,v∈V−U，则必然存在一棵包含边 (u,v)的最小生成树。
Prim算法： 算法思想：设 N=(V,E)是连通网， TE是 N上最小生成树中的边的集合；初始令 U=u0,TE={}；在所有 u∈U,v∈V−U的边(u,v)∈E中，找一条代价最小的边 (u0,v0)；将 (u0,v0)并入边集合 TE，同时将 v0并入 U U U；重复上述操作，直至 U=V为止，则 T=(V,TE)为 N N N的最小生成树。
Kruskal算法： 算法思想：设连通网 N=(V,E)，令最小生成树初始状态是只有n个顶点但是没有边的非连通图T=(V,)，每个顶点自成一个连通分量。在E中选取代价最小的边，若改变依附的顶点落在 T中不同的连通分量上(即不能形成环)，则将此边加入到 T T T中；否则去掉此边，选取下一条代价最小的边；依次类推，直至T中所有顶点都在同一个连通分量上为止。
Prim算法 的时间复杂度为： O(n2)，其中n为顶点数量，所以适用于稠密图；Kruskal算法的时间复杂度为：O(eloge)，其中e为边的数量，所以适用于稀疏图。
4.2 最短路径
交通网络使用有向网来表示：顶点表示地点；弧表示两个地点之间有路连通；弧上的权值表示两个地点之间的距离，交通费或者图中所花费的时间等。如何使得从一个地点到另外一个地点的运输时间最短或者运费最省，这就是一个求两个地点之间的最短路径问题。
问题抽象：在有向网中从源点到终点的多条路径中，寻找一条各边的权值之和最小的路径，即最短路径，最短路径与最小生成树不同，路径上不一定包含n个顶点，也不一定包含n-1条边。
4.2.1 单源最短路径问题-Dijkstra算法
求图中某个顶点到另外其余顶点的最短路径，叫做单源最短路径问题，常用的算法时Dijkstra算法。Dijkstra算法的流程如下所示：
1）初始化：先找出从源点 v0到各终点 v k v_k vk的直达路径 (v0,vk)，即通过一条弧到达的路径；
2）选择：从这些路径中找出一条长度最短的路径 (v0,vu)；
3）更新：然后对其余各条路径进行适当地调整：若在图中存在弧(u,vk)，且(v0,u)+(u,vk)<(v0,vk)，则以路径 (v0,u,vk)代替 (v0,vk)；
4）在调整之后的各条路径中，再找长度最短的路径，以此类推。
Dijkstra算法的示意图如下图所示：
4.2.2 多源最短路径问题-Floyd算法
上述介绍的Dijkstra算法可以计算某个点到其他点的最短路，但是如果想要计算每个点到其他的最短路需要将Dijkstra算法循环顶点个数次。
另外一种求多源最短路径问题的算法时Floyd算法，Floyd算法的思想如下所示：首先进行逐个顶点的额试探；之后从 vi到vj的所有可能存在的路径中，选出一条长度最短的路径。Floyd算法的思路演示如下图所示：
4.3 拓扑排序
拓扑排序和关键路径这两种应用针对的是一种特殊的图-有向无环图，简称DAG图(Directed Acycline Graph)。DAG的示意图如下图所示：
AOV网，用一个有向图表示一个工程的各个子工程机器相互制约的关系，其中以顶点表示活动，弧表示活动之间的优先制约关系，称这种有向图为顶点表示活动的网，简称AOV网-Activity On Vertex network。应用AOV网解决拓扑排序问题。
AOE网，用一个有向图表示一个工程的各个子工程机器相互制约的关系，其中以弧表示活动，顶点表示活动的开始或者结束事件，称这种有向图为边表示活动的网，简称AOE网-Activity On Edge network。应用AOE网解决关键路径问题。
AOV网的特点：若从i到j有一条有向路径，则i是j的前驱，j是i的后继；若<i,j>是网中的有向边，则i是j的直接前驱，j是i的直接后继。AOV网中不允许有回路存在，因为如果有回路存在，则表明某项活动以自己为先决条件，显然这是荒谬的。
在AOV网没有回路的前提下，我们将全部活动排列成一个线性序列，使得若AOV网中有弧<i,j>存在，则在这个序列中，i一定排在j的前面，具有这种性质的线性序列称为拓扑有序序列，相应的拓扑有序排序的算法称为拓扑排序。
拓扑排序的方法：在有向图中选一个没有前驱的顶点并且进行输出；从图中删除该顶点和所有以它为尾的弧；重复上述两步，直至全部顶点均已输出或者当图中不存在无前驱的顶点为止。拓扑排序的示意如下图所示：
检测AOV网中是否存在环的方法：对有向图构造其顶点的拓扑有序序列，若网中所有顶点都在它的拓扑有序序列中，则该AOV网必定不存在环。
4.4 关键路径
把工程计划表示为边，以此来表示活动的网络，即AOV网。用顶点表示时间，弧表示活动，弧的权值表示活动的持续时间。事件表示在它之前的活动已经完成，在它之后的活动可以开始。
关键路径的求解方法可以参考运筹学课程。
