教育部—微软精品课程建设项目 设图G=(V,VR})中的一个顶点序列 uV1.0,Vi,1 ,vmw}中,(w1V1)∈VR1m 则称从顶点u到页点w之间存在一条路径。 路径上边的数目称作路径长度。 如长度为3的路径简单路径序列中顶点 RA, B, C, FS 不重复出现的路径 简单回路:序列中第 个页点和最后一个 6一⑥ 点相同的路径。 南京航空航天大学数据结构课题组版权所有
设图G=(V,{VR})中的一个顶点序列 { u=vi,0,vi,1, …, vi,m=w}中，(vi,j-1 ,vi,j)VR 1≤j≤m, 则称从顶点u 到顶点w 之间存在一条路径。 路径上边的数目称作路径长度。 A B E C F 如:长度为3的路径 {A,B,C,F} 简单路径:序列中顶点 不重复出现的路径。 简单回路:序列中第一 个顶点和最后一个顶 点相同的路径
教育部—微软精品课程建设项目 若图G中任意两个页 B 点之间都有路径相通, 则称此图为连通图;④ 若无向图为非连通图 则图中各个极大连通 子图称作此图的连通 分量。 南京航空航天大学数据结构课题组版权所有
若图G中任意两个顶 点之间都有路径相通， 则称此图为连通图； 若无向图为非连通图， 则图中各个极大连通 子图称作此图的连通 分量。 B A C D F E B A C D F E
教育部—微软精品课程建设项目 对有向图,若任意两个顶点之间都存在 条有向路径,则称此有向图为强连通图。 否则,其各个强连通子图称作它的 强连通分量。 Bk B O⑩ 南京航空航天大学数据结构课题组版权所有
若任意两个顶点之间都存在 一条有向路径，则称此有向图为强连通图。 A B E C F A B E C F 对有向图， 否则，其各个强连通子图称作它的 强连通分量
教育部—微软精品课程建设项目 假设一个连通图有n个顶点和e条边, 其中n-1条边和n个顶点构成一个极小连 通子图,称该极小连通子图为此连通图的 生成树。 对非连通图,则 称由各个连通分 ①量的生成树的集 合为此非连通图 的生成森林。 南京航空航天大学数据结构课题组版权所有
假设一个连通图有 n 个顶点和 e 条边， 其中 n-1 条边和 n 个顶点构成一个极小连 通子图，称该极小连通子图为此连通图的 生成树。 对非连通图，则 称由各个连通分 量的生成树的集 合为此非连通图 的生成森林。 B A C D F E
教育部—微软精品课程建设项目 基本操作 结构的建立和销毁 对顶点的访向操作p 插入或删除顶点 插入和删除弧 对邻接点的操作p 遍历 扇京航航天大学数握题双以有
结构的建立和销毁 插入或删除顶点 对邻接点的操作 对顶点的访问操作 遍历 插入和删除弧 基本操作