第六章图.doc

第六章 图 一、图的定义 图是由顶点的有穷非空集合和顶点之间边的集合组成?G=(V,E) 图的基本术语 1.无向图：图的任意两个顶点之间的边都是无向边 ?有向图：图中存在两个顶点之间的边是有向边 2.简单图：图中不存在顶点到其自身的边，也不存在重复出现的边 3.邻接/依附：在无向图中，对于任意顶点Vi和Vj，若存在边(Vi,Vj)，则称顶点Vi,Vj互为邻接点，边(Vi,Vj)依附于顶点Vi和Vj ????? 在有向图中，对于任意顶点Vi和Vj，若存在弧Vi,Vj，则称顶点Vj是Vi的邻接点，弧Vi,Vj依附于顶点Vi和Vj 4.无向完全图：无向图中任意两个顶点之间都存在边 ?有向完全图：有向图中任意两个顶点之间都存在方向互为相反的两条弧 ?含有n个顶点的无向完全图共有n*(n-1)/2条边；含有n个顶点的有向完全图共有n*(n-1)条边 5.顶点的度： ??(1)无向图中某顶点的度：指依附于该顶点的边的个数 ??(2)有向图中某顶点的入度：指以该顶点为弧头的弧的个数 ??? 有向图中某顶点的出度：指以该顶点为弧尾的弧的个数 ??(3)在有n个顶点e条边的无向图中，所有的顶点度数之和=2e ??? 在有n个顶点e条边的有向图中，所有的顶点的入度之和=所有顶点的出度之和=e 6.权/网：在图中，权通常是指对边赋予的有意义的数值量；边上带权的图称为网或网图 7.路径/路径长度/回路： ??(1)图中两个顶点之间的路径：指这两个顶点之间所有顶点组成的一个顶点序列；顶点不重复出现的路径称为简单路径 ??(2)路径长度：指路径上边的数目 ??(3)回路：指第一个顶点和最后一个顶点相同的路径；除第一个和最后一个顶点之外，其余顶点不重复出现的回路称为简单回路 8.子图：指由某图中顶点集合的子集和边集合的子集构成的图；一个图可以有多个子图 9.连通图,连通分量/强连通图,强连通分量 ??(1)连通图：指任意两个顶点之间均有路径的无向图 ??? 连通分量：指非连通图的极大连通子图(极大是指包含所有连通的顶点及相关联的边) ??(2)强连通图：指任意两个顶点之间相互有路径的有向图 ??? 强连通分量：指非强连通图的极大强连通子图 10.生成树/生成森林 ??(1)连通图的生成树：指只访问每个顶点一次，经过的顶点和边构成的子图，即包含图中所有顶点的一个极小连通子图 ??(2)有向图的生成树：是包含图中所有顶点的一个子图，且该子图只有一个入度为0的顶点，其余顶点入度均为1 ??(3)生成森林：非连通图的每个连通分量都可以得到一棵生成树，这些生成树构成了非连通图的生成森林 ??(4)图的生成树可以在遍历过程中得到，具有n个顶点的生成树有且仅有n-1条边 (5)图的生成树是无环图，且可能不唯一； 图的遍历 图的遍历：从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次,实质上是对每个顶点查找其邻接点的过程 1.遍历可从图中任一顶点出发，一般选择从编号较小的顶点开始，所以采用数组存储图的顶点信息，编号从0开始 2.多次重复从某一顶点出发进行图的遍历，这样就可以遍历到图中所有的顶点 3.为了在遍历过程中便于区分顶点是否已被访问，设置一个访问标识变量数组visited[n]，初值为0 4.图的遍历次序有两种：深度优先遍历和广度优先遍历，对无向图和有向图都试用 ?????深度优先遍历是以递归方式进行的，需用栈记载遍历路线，相当于树的前序遍历； ?????广度优先遍历是以层次方式进行的，需用队列保存已访问的顶点，相当于树的层序遍历； 深度优先遍历和广度优先遍历的遍历结果都可能不唯一； ??(1)深度优先： ??? ①选定起始点V0； ??? ②选择一个与V0邻接且未被访问过的顶点V1； ??? ③从V1出发按邻接方向继续访问，当遇到一个顶点所有邻接点均已被访问时，回到该顶点的前一个点，再寻求未被访问过的邻接点，直到所有顶点都被访问过一次； ??(2)广度优先： ?? ①选定起始点V0； ?? ②访问与V0邻接的所有顶点V1,V2,……,Vk,这些作为第一层遍历结果； ?? ③在第一层遍历结果中选定一个顶点V1为起点； ??? ④重复②③，直到所有节点都被访问过一次； 图的存储结构 ?图包含的信息：顶点信息+顶点之间的邻接关系(边或弧)的信息 图没有顺序存储结构，常用存储结构为：邻接矩阵；邻接表；十字链表；邻接多重表；边集数组 4.1 邻接矩阵 1.邻接矩阵：用一维数组存储顶点信息，二维数组存储顶点之间的邻接关系，这个二维数组称为邻接矩阵，图中若有n个顶点，则邻接矩阵为n*n的方阵arc[n][n] 2.邻接矩阵的求法 ??(1)无/有向图中：若Vi邻接到Vj，则arc