(5)顶点的度:顶点v的度是与它相关联的边的条数,记作 TD(v)。顶点的度=入度+出度 (6)路径:在图G=(V,E)中,着从顶点出发有一组边使可到 达页点%,则称质点v到顶点的顶点序列为从顶点到顶点v 的路径 (7)权:有些图的边附带有数据信息,这些附带的数据信息 称为权。带权的图也称作网络或网。 (8)路径长度:对于不带权的图,一条路径的路径长度是指 该路径上的边的条数;对于带权的图,一条路径的路径长度是 指该路径上各个边权值的总和。 (9)子图:设有图G={VE和图G2={V2E2},着VV2,且 EE2,则称图G2是图G的子图
（5）顶点的度：顶点v的度是与它相关联的边的条数，记作 TD(v)。顶点的度 = 入度 + 出度。 （6）路径：在图G=(V,E)中，若从顶点vi出发有一组边使可到 达顶点vj，则称顶点vi到顶点vj的顶点序列为从顶点vi到顶点vj 的路径 （7）权：有些图的边附带有数据信息，这些附带的数据信息 称为权。带权的图也称作网络或网。 （8）路径长度：对于不带权的图，一条路径的路径长度是指 该路径上的边的条数；对于带权的图，一条路径的路径长度是 指该路径上各个边权值的总和。 （9）子图：设有图G1={V1 ,E1 }和图G2={V2 ,E2 }，若V1V2，且 E1 E2，则称图G2是图G1的子图
B 10 60 12 6 L(3)7 15 3 35 6 E 16 施工进度图 交通网络图
2 1 3 5 4 6 7 8 7 9 6 10 6 127 15 16 3 B A C D E 60 30 45 75 80 40 35 施工进度图 交通网络图
(10)连通图和强连通图:在无向图中,若从顶点v到顶点 有路径,则称顶点和顶点是连通的。如果图中任意对页 点都是连通的,则称该图是连通图 在有向图中,若对于任意一对顶点v和顶点v(vv;)都存在 路径,则称图G是强连通图。 (11)生成树:一个连通图的最小连通子图称作该图的生成 树。有n个顶点的连通图的生成树有n个顶点和m-1条边。 生成树一般是对无向图来讨论。 (12)简单路径和回路:若路径上各顶点v,2…,n互不重复 ,则称这样的路径为简单路径;着路径上第一个顶点v与最后 一个顶点v重合,则称这样的路径为回路或环
（10）连通图和强连通图：在无向图中，若从顶点vi到顶点vj 有路径，则称顶点vi和顶点vj是连通的。如果图中任意一对顶 点都是连通的，则称该图是连通图。 在有向图中，若对于任意一对顶点vi和顶点vj（vi ≠vj）都存在 路径，则称图G是强连通图。 （11）生成树：一个连通图的最小连通子图称作该图的生成 树。有n个顶点的连通图的生成树有n个顶点和n-1条边。 生成树一般是对无向图来讨论。 （12）简单路径和回路：若路径上各顶点v1 ,v2 ,…,vm ,互不重复 ，则称这样的路径为简单路径；若路径上第一个顶点v1与最后 一个顶点vm重合，则称这样的路径为回路或环
2图的抽象数据类型 数据集合:由一组顶点集合v和一组边e集合组成。当为带 权图时每条边上权w还构成权集合Ww 操作集合: (1)初始化 Initiate(G,n (2)插入顶点 Insertvertex( G, vertex) (3)插入边 InsertEdgeG,vL,V2, weight) (4)删除边 Delete Edge(G,v1v2) (5)删除顶点 Delete vertex(G, vertex) (6)第一个邻接顶点 GetFirstvex(G,y) (7)下一个邻接顶点 GetNextvex(G,intv1,v2) (8)遍历 Depth FirstSearch(G
数据集合：由一组顶点集合{vi }和一组边{ej }集合组成。当为带 权图时每条边上权wj还构成权集合{wj }。 操作集合： （1）初始化Initiate(G, n) （2）插入顶点 InsertVertex(G, vertex) （3）插入边InsertEdgeG, v1, v2, weight) （4）删除边DeleteEdge(G, v1, v2) （5）删除顶点DeleteVertex(G, vertex) （6）第一个邻接顶点GetFirstVex(G, v) （7）下一个邻接顶点GetNextVex(G, int v1, v2) （8）遍历DepthFirstSearch(G) 2.图的抽象数据类型
92图的存储结构 图的存储结构主要有邻接矩阵和邻接表两种。 1.图的邻接矩阵存储结构 假设图G=(V,E有n个顶点,即{v,…,n},E可用如下 形式的矩阵4描述,对于中的每一个元素an,满足 若(vv)∈E或<v,v>∈E 否则 由于矩阵A中的元素a1表示了顶点v和顶点v之间边的关系, 或者说,A中的元素a表示了顶点和页点(0产m1)的 邻接关系,所以矩阵A称作邻接矩阵
9.2 图的存储结构 图的存储结构主要有邻接矩阵和邻接表两种。 1.图的邻接矩阵存储结构 = 否则 若 或 0 1 (v ,v ) E v ,v E a i j i j ij 假设图G=(V,E)有n个顶点，即V={v0 ,v1 ,…,vn-1 }，E可用如下 形式的矩阵A描述，对于A中的每一个元素aij，满足： 由于矩阵A中的元素aij表示了顶点vi和顶点vj之间边的关系， 或者说，A中的元素aij表示了顶点vi和顶点vj（0≤j≤n-1）的 邻接关系，所以矩阵A称作邻接矩阵