图第七章概述7.1·7.2图的存储结构邻接矩阵图类7.37.4图的遍历
第七章 图 • 7.1 概述 • 7.2 图的存储结构 • 7.3 邻接矩阵图类 • 7.4 图的遍历
7.1 概述7.1.1图的基本概念1、图：由结点集合及结点间的关系集合组成的一种数据结构。记为G=（V，E），其中：V是G的顶点集合；G的边集合。2、有向图：图G中的每条边都是有方向的；<v1，v3>3、无向图：图G中的每条边都是无方向的；（vl,v4)<vl,v4><v4,vl>4、完全图：图G任意两个顶点都有一条边相连接：*若n个顶点的无向图有n(n-1)/2条边，称为无向完全图若n个顶点的有向图有n(n-1）条边，称为有向完全图Iv5V(a)有向图(b)无向图（c）无向完全图(d）有向完全图
7.1 概述 7.1.1 图的基本概念 １、图：由结点集合及结点间的关系集合组成的一种数据结构。 记为G＝( V, E )，其中：V是G的顶点集合；E是G的边集合。 v1 v2 v3 v4 2、有向图：图G中的每条边都是有方向的；<v1,v3> ３、无向图：图G中的每条边都是无方向的；(v1,v4) ４、完全图：图G任意两个顶点都有一条边相连接； ❖若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 ❖若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 1 2 3 1 4 2 3 4 <v1,v4><v4,v1> (a)有向图 (b)无向图 (c)无向完全图 (d)有向完全图 v1 v2 v3 v4 v5
5、子图：设有两个图G1=(V1,EI)和G2=(V2,E2)。若V2 CV1且E2CE1,则称图G2是图G1的子图。(a)图1(b)图26、带权图：指边上带权的图。其中权是指每条边标上具有与该边相关的数据信息。10604080753015354516(a)(b)
5、子图：设有两个图G1＝(V1, E1) 和 G2＝(V2, E2)。若 V2 V1 且 E2 E1, 则称 图G2 是 图G1 的子图。 (a)图1 (b)图２ 6、带权图：指边上带权的图。其中权是指每条边标上具有与 该边相关的数据信息。 2 1 3 5 4 6 7 8 7 9 6 10 6 12 7 15 16 3 B A C D E 60 30 45 75 80 40 35 (a) (b)
7、路径：在图G（V、E)中，若从顶点V；出发，沿一些边经过顶点Vpl,Vp2,.Vpm，到达顶点vjo则称顶点序列（vi,Vpl,Vp2,…Vpm，y）_为从顶点vi到顶点v,的路径。路径长度：非带权图的路径长度是指此路径上边的条数；带权图的路径长度是指路径上各边的权之和。1060408075153035H4516(a)(b)8、简单路径：路径上各顶点V1,V2.Vm均不互相重复。9、回路：若路径上第一个顶点V1与最后一个顶点Vm重合，则称这样的路径为回路或环
７、路径：在图G＝(V, E)中,若从顶点 vi 出发,沿一些边经过 顶点vp1,vp2,.,vpm，到达顶点vj。则称顶点序列(vi,vp1,vp2,., vpm ,vj ) 为从顶点vi 到顶点 vj 的路径。 路径长度：非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。 ８、简单路径：路径上各顶点 v1 ,v2 ,.,vm 均不互相重复。 ９、回路：若路径上第一个顶点 v1 与最后一个顶点vm 重合，则 称这样的路径为回路或环。 2 1 3 5 4 6 7 8 7 9 6 10 6 12 7 15 16 3 B A C D E 60 30 45 75 80 40 35 (a) (b)
则称顶10、连通图：在无向图中，若从顶点v到顶点v有路径，点,与v,是连通的。如果图中任意一对顶点都是连通的，则称此图是连通图。都存在11、强连通图：在有向图中，若对于每一对顶点v;和vi,一条从V到v:和从v到v;的路径，则称此图是强连通图
10、连通图：在无向图中, 若从顶点v1到顶点v2有路径, 则称顶 点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此 图是连通图。 11、强连通图：在有向图中, 若对于每一对顶点vi和vj, 都存在 一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。 0 1 3 2 0 1 2 3