第8章图 8.1图 8.2图的存储结构 8.3图的实现 8.4图的遍历 8.5最小生成树 8.6最短路径
1 8.1 图 8.2 图的存储结构 8.3 图的实现 8.4 图的遍历 8.5 最小生成树 8.6 最短路径 第8章 图
8.1图 图的基本概念 图:由结点集合及结点间的关系集合组成的一种数据结构 记为G=(V,E),其中:是顶点集合,是有穷非空集;E 是的边集合,是有穷集。 2、有向图:图G中的每条边都是有方向的; 3、无向图:图G中的每条边都是无方向的; 4、完全图:图G任意两个顶点都有一条边相连接; 若n个顶点的无向图有m(n-1)2条边,称为无向完全图 若n个顶点的有向图有n(m-1)条边,称为有向完全图 v2 53 (a)有向图(b)有向图(c)无向完全(d
2 ８.1 图 一、图的基本概念 １、图：由结点集合及结点间的关系集合组成的一种数据结构。 记为G＝( V, E )，其中：V是G的顶点集合，是有穷非空集；E 是G的边集合，是有穷集。 v1 v2 v3 v4 v5 v1 v2 v3 v4 2、有向图：图G中的每条边都是有方向的； ３、无向图：图G中的每条边都是无方向的； ４、完全图：图G任意两个顶点都有一条边相连接； ❖若 n 个顶点的无向图有 n(n-1)/2 条边, 称为无向完全图 ❖若 n 个顶点的有向图有n(n-1) 条边, 称为有向完全图 (a)有向图 (b)有向图 (c)无向完全图 (d)有向完全图 1 2 3 1 4 2 3 4
子图:设有两个图G=(H,E1)和G2=(2,E2)。若g V且E2cE,则称图G2是图G1的子图。 (2 (a)图1 (b)图2 6、带权图:指边上带权的图。其中权是指每条边标上具有与 该边相关的数据信息。 7、路径:在图G=(E中,若从顶点v出发,沿一些边经过 顶点 V,到达顶点v。则称顶点序列(v,V,V… pl 为从顶点v到顶点v的路径 路径长度:非带权图的路径长度是指此路径上边的条数; 带权图的路径长度是指路径上各边的权之和。 8、简单路径:路径上各顶点Ⅵ1,V2…Vm均不互相重复。 9、回路:若路径上第一个顶点v1与最后一个顶点vm重合,则 称这样的路径为回路或环
3 5、子图：设有两个图G1＝(V1, E1) 和 G2＝(V2, E2)。若 V2 V1 且 E2 E1, 则称 图G2 是 图G1 的子图。 (a)图1 (b)图２ ７、路径：在图G＝(V, E)中,若从顶点 vi 出发,沿一些边经过 一顶点vp1,vp2,…,vpm，到达顶点vj。则称顶点序列(vi,vp1,vp2,…, vpm ,vj ) 为从顶点vi 到顶点 vj 的路径。 路径长度：非带权图的路径长度是指此路径上边的条数； 带权图的路径长度是指路径上各边的权之和。 6、带权图：指边上带权的图。其中权是指每条边标上具有与 该边相关的数据信息。 ８、简单路径：路径上各顶点 v1 ,v2 ,...,vm 均不互相重复。 ９、回路：若路径上第一个顶点 v1 与最后一个顶点vm 重合，则 称这样的路径为回路或环
10、连通图:在无向图中,若从顶点到顶点v有路径,则称顶 点n与吃是连通的。如果图中任意一对顶点都是连通的,则称此 图是连通图。 非连通图的极大连通子图叫做连通分量 11、强连通图:在有向图中,若对于每一对顶点v和v,都存在 条从v到v;和从v到v的路径,则称此图是强连通图 非强连通图的极大强连通子图叫做强连通分量 12、生成树:是一个极小连通子图,它含有图中全部n个顶点,但 只有m1条边。 13、结点的度:结点v的度是与它相关联的边的条数。记作TD(v) 在有向图中,结点的度等于该结点的入度与出度之和。其中结点 ⅴ的入度是以ⅴ为终点的有向边的条数,记作1D(v);结点v的 出度是以v为始点的有向边的条数,记作0D(v)。 14、邻接结点:若(u,v)是E(G)中的一条边,则称u与v互为邻 接结点
4 10、连通图：在无向图中, 若从顶点v1到顶点v2有路径, 则称顶 点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此 图是连通图。 非连通图的极大连通子图叫做连通分量。 11、强连通图：在有向图中, 若对于每一对顶点vi和vj, 都存在 一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。 非强连通图的极大强连通子图叫做强连通分量。 12、生成树：是一个极小连通子图，它含有图中全部n个顶点，但 只有n-1条边。 13、结点的度：结点v的度是与它相关联的边的条数。记作TD(v)。 在有向图中, 结点的度等于该结点的入度与出度之和。其中结点 v 的入度是以 v 为终点的有向边的条数, 记作 ID(v);结点 v 的 出度是以 v 为始点的有向边的条数, 记作 OD(v)。 14、邻接结点：若 (u, v) 是 E(G) 中的一条边，则称 u 与 v 互为邻 接结点
图的抽象数据类型 数据集合:由一组结点集合{;}和一组边集合{e}组成。当为 带权图时每条边上权w构成权集合{w} 操作集合: 1)初始化 Initiate(G,n) (2)插入结点 InsertVertex( G, vertex) (3)插入边 InsertEdge(Gv1,v2, weight) (4)删除边 Delete Edge〔GvL,v2) (5删除结点 Deete vertex( G, vertex) (6)第一个邻接结点 GetFirstVex(Gv) (7)下一个邻接结点 GetNextVex(GV1v2)
5 数据集合：由一组结点集合｛v i ｝和一组边集合{ej }组成。当为 带权图时每条边上权wi构成权集合{wi }。 操作集合： (1)初始化Initiate(G,n) (2)插入结点InsertVertex(G,vertex) (3)插入边InsertEdge(G,v1,v2,weight) (4)删除边DeleteEdge（G,v1,v2) (5)删除结点DeeteVertex(G,vertex) (6)第一个邻接结点GetFirstVex(G,v) (7)下一个邻接结点GetNextVex(G,v1,v2) 二、图的抽象数据类型