人民邮电出版社：高职高专现代信息技术系列教材《数据结构》课程电子教案（PPT课件讲稿）第六章 图

第6章图 本章中介绍下列主要内容: ●图的定义 ●图的存储结构 ●图的遍历操作 ●图的几个典型问题 请单赤鼠标左键换页! 退出

第6章 图 本章中介绍下列主要内容： ⚫ 图的定义 ⚫ 图的存储结构 ⚫ 图的遍历操作 ⚫ 图的几个典型问题 退出

6.1图的定义 6.2图的存值结构 6.3图的遍历 6.4最小生成树问题 6.5拓扑序问题 请单赤鼠标左键换页!

6.1 图的定义 6.2 图的存储结构 6.3 图的遍历 6.4 最小生成树问题 6.5 拓扑排序问题

6.1图的定义 6.1.1定义 图是由结点的有穷集合V和边的集合E组成。其中, 为了与树形结构加以区别,在图结构中常常将结点称 为顶点,边是顶点的有序偶对,若两个顶点之间存在 条边,就表示这两个顶点具有相邻关系。 请单鼠标左键换页!

6.1 图的定义 6.1.1 定义 图是由结点的有穷集合V和边的集合E组成。其中， 为了与树形结构加以区别，在图结构中常常将结点称 为顶点，边是顶点的有序偶对，若两个顶点之间存在 一条边，就表示这两个顶点具有相邻关系

v 4-(w> 图6-1 请单鼠标左键换页!

图 6 - 1 (a) (b)

在上面两个图结构中,一个是有向图,即每条 边都有方向,另一个是无向图,即每条边都没有方 向 在有向图中,通常将边称作弧,含箭头的一端 称为弧头,另一端称为弧尾,记作两条弧。若无向图中有n个顶点,则 最多有n(n-)2条边,我们又将具有n(n-1)/2条边的 无向图称作无向完全图 请单赤鼠标左键换页!

在上面两个图结构中，一个是有向图，即每条 边都有方向，另一个是无向图，即每条边都没有方 向。 在有向图中，通常将边称作弧，含箭头的一端 称为弧头，另一端称为弧尾，记作，它表示 从顶点vi到顶点vj有一条边。 若有向图中有n个顶点，则最多有n(n-1)条弧， 我们又将具有n(n-1)条弧的有向图称作有向完全图。 以顶点v为弧尾的弧的数目称作顶点v的出度， 以顶点v为弧头的弧的数目称作顶点v的入度。 在无向图中，边记作(vi ,vj )，它蕴涵着存在和两条弧。若无向图中有n个顶点，则 最多有n(n-1)/2条边，我们又将具有n(n-1)/2条边的 无向图称作无向完全图

与顶点v相关的边的条数称作顶点v的度。 路径长度是指路径上边或弧的数目。 若第一个顶点和最后一个顶点相同,则这条路 径是一条回路。 若路径中顶点没有重复出现,则称这条路径为 简单路径。 在无向图中,如果从顶点v到顶点v有路径, 则称v和y连通。如果图中任意两个顶点之间都连通, 则称该图为连通图,否则,将其中的极大连通子图称 为连通分量。 在有向图中,如果对于每一对顶点v和y,从v 到v和从v到v都有路径,则称该图为强连通图;否则, 将其中的极大连通子图称为强连通分量。 请单赤鼠标左键换页!

与顶点v相关的边的条数称作顶点v的度。 路径长度是指路径上边或弧的数目。 若第一个顶点和最后一个顶点相同，则这条路 径是一条回路。 若路径中顶点没有重复出现，则称这条路径为 简单路径。 在无向图中，如果从顶点vi到顶点vj有路径， 则称vi和vj连通。如果图中任意两个顶点之间都连通， 则称该图为连通图，否则，将其中的极大连通子图称 为连通分量。 在有向图中，如果对于每一对顶点vi和vj，从vi 到vj和从vj到vi都有路径，则称该图为强连通图；否则， 将其中的极大连通子图称为强连通分量

6.1.2图的基本操作一 基本操作: (1)创建一个图结构 Create Graph(G) (2)检索给定顶点 Locate vex(G,item) (3)获取图中某个顶点 Get vex(G,) (4)为图中顶点赋值 Putvex(G,w, valuel) (5)返回第一个邻接点 FirstAdjVex(G,y) (6)返回下一个邻接点 NextAdjVex(Gv,w) (7)插入一个顶点 Insert vex(G,v) (8)删除一个顶点 Delete vex(G,v) (9)插入一条边 Inserted(G,V,w) (10)删除一条边 Delete edge(G,V,w) 11)遍历图 Traverse(G,v) 请单鼠标左键换页!

6.1.2 图的基本操作 基本操作： （1）创建一个图结构 CreateGraph(G) （2）检索给定顶点LocateVex(G,item) （3）获取图中某个顶点 GetVex(G,v) （4）为图中顶点赋值 PutVex(G,v,value) （5）返回第一个邻接点 FirstAdjVex(G,v) （6）返回下一个邻接点 NextAdjVex(G,v,w) （7）插入一个顶点 InsertVex(G,v) （8）删除一个顶点 DeleteVex(G,v) （9）插入一条边 InsertEdge(G,v,w) （10）删除一条边DeleteEdge(G,v,w) （11）遍历图Traverse(G,v)

6.2图的存信结构 6.2.1邻接矩阵 有向图的邻接矩阵 具有n个顶点的有向图可以用一个nXn的方形矩阵 表示。假设该矩阵的名称为M,则当y>是该有向 图中的一条弧时,M[ij-1;否则M[ij=0。第个顶点 的出度为矩阵中第中“1”的个数;入度为第列中 1”的个数,并且有向图弧的条数等于矩阵中“1”的 数。 请单赤鼠标左键换页!

6.2 图的存储结构 6.2.1 邻接矩阵 1. 有向图的邻接矩阵 具有n个顶点的有向图可以用一个nn的方形矩阵 表示。假设该矩阵的名称为M，则当是该有向 图中的一条弧时，M[i,j]=1；否则M[i,j]=0。第i个顶点 的出度为矩阵中第i行中“1”的个数；入度为第i列中 “1”的个数，并且有向图弧的条数等于矩阵中“1”的 个数

1.2无向图的邻接矩阵 具有n个顶点的无向图也可以用一个nXn的方形矩 阵表示。假设该矩阵的名称为M,则当(v;v;)是该无 向图中的一条边时,M[=Mi,=1;否则, M[ijl=Mij-=0。第i个顶点的度为矩阵中第i行中“1” 的个数或第列中“1”的个数。图中边的数目等于矩阵 中“1的个数的一半,这是因为每条边在矩阵中描述 了两次。 请单赤鼠标左键换页!

1．2 无向图的邻接矩阵 具有n个顶点的无向图也可以用一个nn的方形矩 阵表示。假设该矩阵的名称为M，则当（vi ,vj）是该无 向图中的一条边时，M[i,j]=M[j,i]=1；否则， M[i,j]=M[j,j]=0。第i个顶点的度为矩阵中第i行中“1” 的个数或第i列中“1”的个数。图中边的数目等于矩阵 中“1”的个数的一半，这是因为每条边在矩阵中描述 了两次

01000 00110 M=00010 0000 00100 图6-4 请单鼠标左键换页!

图 6-4