数据结构与算法11.ppt

文档介绍：数据结构与算法 Chapter 10 图--1 3 图的基本概念?一个图 G= (V,E)是一个由非空的有限集 V和一个边集 E 所组成的。若 E中的每条边都是结点的有序对( v 1 , v 2),就说该图是有向图( directed graph , digraph )。若 E中的每条边是两个不同结点有序对,就说该图是无向图,其边仍表示成( v 1 , v 2) 124 356 7 8 顶点边 124 356 7 8 1 {v 1,v2,v3,v4,v5,v6,v7, v8} { (v1,v2)(v1,v3)(v2,v3)(v2,v5) (v2,v4)(v3,v5)(v4,v5)(v4,v 6)(v4,v7) (v5,v7)(v5,v8)(v6,v7)(v7,v 8)} 无向图图的表示 124 356 7 8 有权图 90 60 120 50 20 0 40 110 160 70 75 80 180 124 356 7 8 顶点弧 1 {v 1,v2,v3,v4,v5,v6,v7, v8} { <v1,v2><v1,v3><v2,v4><v2,v5 ><v3,v2><v3,v5><v4,v6><v4, v7><v5,v4><v5,v7><v5,v8><v 7,v6><v7,v8>} 有向图完全图:n个节点的图中,若是无向图,有 n(n-1)/2 条边;若是有向图,有 n(n-1) 条边。权:图中边或弧上的值。邻接顶点:有边或弧相连的顶点。顶点的度:顶点所连接的边或弧的数量,称为该顶点的度。指向顶点的弧的数量叫入度,由顶点出发的弧,称为该顶点的出度。图的基本术语路径与回路:邻接顶点所形成序列称为路径。路径长度:无权图上,路径上边的数目称为路径长度;有权图上,路径上边的权重之和为路径长度。回路/环:如果路径的起点和终点相同,则称此路径为回路或环。简单路径:路径上无重复顶点的路径。连通:若图上两个顶点之间有路径,则称为这两点是连通的。连通图:若图上任意两点都是连通的,则为连通图。非连通图:图上存在节点之间不连通的顶点,则为非连通图。连通分量:非连通图的极大连通子图称为连通分量。图的基本术语图的操作?图的建立?顶点定位?取顶点值?求顶点的第一邻接点及求下一邻接点?插入新顶点及删除顶点?插入一条弧或删除一条弧?遍历图(广度优先/深度优先) 图的表示—邻接矩阵设图 G = ( V, E ) , V = { 0 ,1,…, n-1 } 则表示 G的邻接矩阵 A 是其元素按下式定义的 n*n矩阵:无向图: 有向图: 带权的有向图: