图论基础知识

(n阶e条边):Р邻接矩阵Р边集数组Р邻接表Р优点Р直观方便,A[i,j]?时间O(1)Р存储稀疏图时,空间效率比较好,也比较直观Р便于查找任一顶点的关联边及关联点,查找运算的时间复杂性平均为O(e/n)Р缺点Р存储稀疏图,会造成很大的空间浪费Р不适合对顶点的运算和对任意一条边的运算Р要查找一个顶点的前驱顶点和以此顶点为终点的边、以及该顶点的入度就不方便了,需要扫描整个表,时间复杂度为O(n+e)。可以用十字邻接表改进Р适用?场合Р处理1个顶点的度和关联边,O(n)Р适合于存储稀疏图和那些对边依次进行处理的运算Р对任一顶点的关联边(顶点)进行不断、重复的运算Р空间?复杂度РO(n*n)РO(3e)Р≈ O(6e+2n)Р常州市第一中学林厚从Р图论算法与实现Р一、图论基础知识Р4、图的遍历:Р从图中某一顶点出发系统地访问图中所有顶点,使每个顶点恰好被访问一次,这种运算操作被称为图的遍历。为了避免重复访问某个顶点,可以设一个标志数组visited[i],未访问时值为false,访问一次后就改为true。? 图的遍历分为深度优先遍历和广度(宽度)优先遍历两种方法。Р图的深度优先遍历:类似于树的先序遍历。从图中某个顶点Vi出发, 访问此顶点并作已访问标记,然后从Vi的一个未被访问过的邻接点Vj出发再进行深度优先遍历,当Vi的所有邻接点都被访问过时,则退回到上一个顶点Vk,再从Vk的另一个未被访问过的邻接点出发进行深度优先遍历,直至图中所有顶点都被访问到为止。Р常州市第一中学林厚从Р图论算法与实现Р一、图论基础知识Р4、图的遍历:Р左图从顶点a出发,进行深度优先遍历的结果为:a,b,c,d,e,g,f?右图从V1出发进行深度优先遍历的结果为:V1,V2,V4,V8,V5,V3,V6,V7Р对下面两个图分别进行深度优先遍历,写出遍历结果。注意:分别从a和V1出发。Р常州市第一中学林厚从