深度优先搜索DFS：【与树的先序遍历类似】1）首先访问起始顶点v2）接着由v出发访问v的任意一个邻接且未被访问的邻接顶点wi3）然后再访问与wi邻接且未被访问的任意顶点yi4）若wi没有邻接且未被访问的顶点时，退回到它的上一层顶点v5）重复上述过程，...

生成树：连通图包含全部顶点的一个极小连通子图 最小生成树：对于带权无向连通图G=(V,E)，G的所有生成树当中边的权值之和最小的生成树为G的最小生成树（MST） 性质：1）最小生成树不一定唯一，即最小生成树的树形不一定唯一，当带权无向连通图...

最短路径：两个顶点之间带权路径长度最短的路径为最短路径 在带权图当中，把从一个顶点v到另一个顶点u所经历的边的权值之和称为路径的带权路径长度 Dijkstra算法：带权图单源最短路径 时间复杂度：O(|V|^2) Dijkstra算法并不适用于含有负...

有向无环图：不存在环的有向图，简称DAG图 在一个表示工程的有向图中，用顶点表示活动，用弧表示活动之间的优先关系，称这样的有向图为顶点表示活动的网，简称AOV网 在AOV网中，不能出现回路 若从顶点vi到vj有一条路径，则在顶点序列中顶点vi必在vj...