个人总结——图.doc

图 数据结构1、 图的定义与术语（一）关于图1、 图：由结点与边组成的。2、 顶点：图结构中的结点。3、 边：顶点的有序偶对。4、 相邻关系：2个顶点之间有边，即表示此2点相邻关系。（二）关于有向图1、有向图：每条边都有方向。2、弧:有向图中的边。记作：表示从顶点vi 到顶点 vj有一条边。3、弧头：含箭头的一端。4、弧尾：不含箭头的一端。5、有向完全图：具有n(n -1) 条边的有向图（有n个顶点）。（有向图最多有n(n -1) 条边）每个顶点有n-1条弧 有n个顶点。即n(n -1) 条有向边6、顶点的出度：以某个顶点为弧尾的弧的数目，称为此点的出度。7、顶点的入度：以某个顶点为弧头的弧的数目，称为此点的入度。（3） 关于无向图1、 无向图：每条边都没有方向。2、 无向图的边：记作(vi ，vj)它蕴含着包括2条弧3、无向完全图：具有n(n -1)/2条边的无向图（有n个顶点）。（无向图最多有n(n -1)/2条边）每个顶点有n-1条弧 有n个顶点。即n(n -1)/2 条边4、顶点的度：与该顶点有关的边的条数。5、连通：2个顶点之间有路径。6、连通图：任意2点之间都连通。此图为连通图。7、连通分量：不是连通图的无向图，将其中的极大连通子图称为连通分量。（4） 关于路径1、 路径长度是指路径上 边或弧的数目。2、 回路：第一个顶点和最后一个顶点相同。3、 简单路径：路径中顶点没有重复出现。2、 图的两种存储方法邻接矩阵法：（1） 有向图的邻接矩阵表示方法1、 有向图的邻接矩阵：具有N个顶点的有向图，可以用一个N*N的方阵表示，有弧1。2、 顶点的出度：为该矩阵中该顶点i,第i行中“1”的个数。（即以该顶点为尾的弧）3、 顶点的入度：为该矩阵中该顶点i,第i列中“1”的个数。（即以该顶点为头的弧）4、 图的边数：为所有“1”个数的一半，因为每条边在矩阵中描述2遍。5、 顶点的度 = 第 i 行元素之和 + 第 i 列元素之和；6、有向图的邻接矩阵是非对称的。（2） 无向图的邻接矩阵表示方法1、 无向图的邻接矩阵：具有N个顶点的有向图，可以用一个N*N的方阵表示，有边1。2、 顶点i的度 = 第 i 行 （或列）中1的个数。3、 无向图的邻接矩阵是对称的。4、 完全图的邻接矩阵中，对角元素为0 ，其余为1。邻接表法：Adjvex next边节点的结构为：Adjvex 是该边或弧依附的顶点在数组中的下标。next是指向下一条边或弧结点的指针。Item firstedge构成以为数组的顶点结构为：Item指的是顶点的内容。Firstedge是指向第一条边或弧结点的指针。邻接矩阵与邻接表比较：对于任一无向图，邻接矩阵唯一，但邻接表不唯一；空间效率：*邻接矩阵 ： O(n2)有向邻接表 ： O(n + e)无相邻接表 ： O(n +2e)邻接矩阵多用于稠密图，邻接链表多用于稀疏图。3、 图的遍历操作1、 深度优先遍历（DFS）类似于树的先序遍历描述：从图中某个顶点V出发，访问该项顶点，然后依次从V的未被访问的邻接点出发继续深度优先遍历图中的其余顶点，直至图中所有与V有路径相通的顶点都被访问完为止。2、 广度优先遍历（BFS）描述：从图中某个顶点V出发，访问该顶点之后，依次访问V的所有未被访问过的邻接点，然后再访问顺序应保持先被访问的顶点其邻接点也优先被访问，知道图中的所有顶点都被访问为止。3、DFS 和 BFS用邻接矩阵表示图 *时间复杂度为： O(n2)用邻接表标示图 *时间复杂度为： O(n+e)空间复杂度相同*都是： O(n)4、 图的应用1、 最小生成树生成树：对于一个拥有N个顶点的无向连通图，它的变数一定多余N-1条，若从中选择N-1条边，使得无向图仍然连通，则由N个顶点，及这N-1条边（弧）组成的图被称为原无向图的生成树。权：在一个图中，每条边或弧可以拥有一个与之相关的数值，我们将它称为权。网：带权的图。最小生成树：权值综合最小的生成树称为最小生成树。构造最小生成树的方法：首先选择一个顶点作为根节点，然后每次从不在生成树中的边种选择一条权值尽可能小的边。为了保证加入到生成树中的边，不会造成回路，与该边临街的2个顶点必须一个已经在生成树中。一个则不在生成树中。2、 拓扑排序（有向图的重要操作）拓扑序列：在给定的有向图G中，若顶点序列vi1 vi2 .vin满足下列条件：有向图G中从顶点vi 必在顶点vj之前，便称这个序列为一个拓扑序列。拓扑排序：求一个有向图的拓扑序列的过程称为拓扑排序。拓扑