《数据结构PPT教学课件-第7章 图》由会员分享，可在线阅读，更多相关《数据结构PPT教学课件-第7章 图（145页珍藏版）》请在金锄头文库上搜索。
1、7.1 图的基本概念和术语 7.2 图的存储结构 7.3 图的遍历和求图的连通分量 7.4 图的生成树 7.5 最短路径 7.6 有向无环图及应用 7.7 图的,第7章 图,返回主目录,第7章 图,7.1 图的基本概念和术语 7.1.1图的基本概念 图G由集合V和E组成, 记为G=(V,E),图中的结点又称为顶点, 其中V是顶点的非空有穷集合, 相关的顶点的偶对称为边, E是边的有穷集合。 若图中的边是顶点的有序对, 则称此图为有向图。 有向边又称为弧, 通常用尖括弧表示一条有向边, vi, vj表示从顶点vi到vj的一段弧, vi称为边的始点(或尾顶点), vj称为边的终点(或头顶点), v
2、i,vj和 vj, vi代表两条不同的弧。 ,若图中的边是顶点的无序对, 则称此图为无向图。 通常用圆括号表示无向边, (vi, vj)表示顶点vi和vj间相连的边。在无向图中(vi, vj)和(vi, vj)表示同一条边, 如果顶点vi 、 vj之间有边(vi, vj), 则vi 、 vj互称为邻接点。 图7.1给出两个图G1和G2, 其中G1是无向图, G2是有向图。在有向图中用箭头表示弧的方向, 箭头从始点指向终点。 图G1是一个无向图的例子。在图G1中,V=v1, v2, v3, v4,E=(v1, v2),(v2, v3),(v1, v3),(v1, v4),(v3, v4)。 而(
3、v2, v1)与（ v1, v2 ）表示同一条边, (v2, v3)与(v3, v2)也表示同一条边, 等。 ,图G2是一个有向图的例子, 在图G2中V=v1, v2, v3, E= v1, v2 , v1, v3 , v2, v3, , v3, v2 。 而 v3, v2 与 v2, v3, 表示两条不同的边。 对于图G=(V,E),G=(V,E),若有VV, EE, 则称图G是G的一个子图。 图7.2给出了G3与其子图G3 。 在下面的讨论中不考虑顶点到自身的边, 也不允许一条边(或弧)在图中重复出现。因此有n个顶点的无向图最大边数为C2n=n(n-1)/2, 这样的图称为无向完全图；有向
4、图中最多可能有A2n=n(n-1)条弧, 这样的图称为有向完全图。 ,7.1.2 路径和回路 所谓顶点vp 到顶点vq之间的路径, 是指顶点序列vp, vi1 , vi2 , , vim, vq, 其中（ vp, vi1）, （ vi1 , vi2）, , （ vim, vq ）分别为图中的边。 路径上边的数目称为路径长度。图7.3所示的无向图中, 顶点v1(注： v1在图中用数字1表示，其余类同)到顶点v5的路径有两条, 分别为v1, v2, v3, v4与v1, v5, v4, 路径长度分别为3和2。 如果路径的起点和终点相同(即vp = vq), 则称此路径为回路或环。序列中顶点不重复出
5、现的路径称为简单路径, 图7.3所示的v1到v5的两条路径都为简单路径。 除第一顶点与最后一个顶点之外, 其它顶点不重复出现的回路为简单回路或者简单环。,7.1.3 连通图 若从顶点vi到顶点vj(ij)有路径, 则vi和vj是连通的。 如果无向图中任意两个顶点vi和vj都是连通的, 则称无向图是连通的。 无向图中极大连通子图称为连通分量。图7.2中的G3有两个连通分量, 见图7.4(a)。 对于有向图来说, 图中任意一对顶点vi和vj(ij)均有从vi到 vj及从 vj到 vi的有向路径, 则称该有向图是强连通的。有向图中的极大强连通子图称为该有向图的强连通分量。 图7.1中G2不是强连通的
6、, 但它有一个强连通分量, 见图7.4(b)。 ,7.1.4 顶点的度 顶点的度是指依附于某顶点vi的边数, 通常记为TD(vi)。在有向图中, 要区别顶点的入度和出度的概念。所谓顶点vi的入度是指以vi为终点的弧的数目, 记为ID(vi); 所谓顶点vi的出度是指以vi为始点的弧的数目, 记为OD(vi)。显然 TD(vi)=ID(vi)+OD(vi) 例如, 在G1中顶点v1的度TD(v1)=3, 在G2中顶点v2的入度ID(v2)=2, 出度OD(v2)=1, TD(v2)=3。 可以证明, 对于具有n个顶点、e条边的图, 顶点vi的度TD(vi)与顶点的个数及边的数目满足关系: ,7.
7、2 图的存储结构,7.2.1 邻接矩阵 图的邻接矩阵表示法是用一个二维数组来表示图中顶点之间的相邻关系。 设图G=(V, E)有n(n1)个顶点, 则G的邻接矩阵是按如下定义的n阶方阵: aij= 1 若(vi,vj)或E(G) 0 反之 例如, 图7.1中的G1、 G2的邻接矩阵分别表示为A1和A2, 矩阵的行、 列号对应于图中结点的号。 ,从图的邻接矩阵表示法中很容易看出图的一些特性, 这种表示方法具有以下特点: (1) 无向图的邻接矩阵一定是对称的, 而有向图的邻接矩阵不一定对称。因此, 用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵; 对有n个顶点的无向图则只需
8、存入上(下)三角形, 故只需n(n+1)/2个单元。,0 1 1 1 1 0 1 0 1 1 0 1 1 0 1 0,A2=,0 1 1 0 0 1 0 1 0,7.2.2 邻接链表 图的邻接链表存储结构是一种顺序分配和链式分配相结合的存储结构。它包括两个部分, 一部分是链表, 另一部分是向量。 在链表部分中共有n个链表(n为顶点数), 即每个顶点对应一个链表。每个链表由一个表头结点和若干个表结点组成。表头结点用来指示第i个顶点vi所对应的链表; 表结点由顶点域(vex)和链域(link)所组成。顶点域指示了与vi相邻接的顶点的序号, 所以一个表结点实际上代表了一条依附于vi的边, 链域指示了
9、依附于vi的下一条边的结点。因此, 第i个链表就表示了依附于顶点vi的所有的边。对于有向图来说, 第i个链表就表示了从vi发出的所有的弧。 ,邻接链表的另一部分是一个向量, 用来存储n个结点。向量的下标指示了顶点的序号, 这样就可以随机地访问任一个顶点的链表。例如, 对于图7.1中的G1和G2, 其邻接链表如图7.5所示。 define MaxSize 20WB typedef struct ArcNode int adjvex; /*该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /*指向下一条弧的指针 */ InfoType info /*该弧相关信息的指针
10、 */ ArcNode;,typedef struct Vnode VertexType data; /*顶点信息 */ ArcNode *firstarc; /*指向第一条依附该顶点的弧的指针 */ Vnode, AdjListMaxSize; typedef struct AdjList vertices; int vexnum, arcnum; ALGraph;HT5SS,若无向图有n个顶点, e条边, 则邻接链表需n个表头结点和2e个表结点, 每个表结点有两个域。 显然, 对于边很少的图, 用邻接链表比用邻接矩阵要节省存储单元。 在无向图的邻接链表中, 第i个链表中的表结点数就是顶点v
11、i的度数。 在有向图的邻接链表中, 第i个链表中的表结点数就是顶点vi的出度。若要求vi的入度, 必须对邻接链表进行扫描, 统计点域的值为i的表结点的数目, 显然, 这是很费时间的。为了便于确定有向图中顶点的入度, 可以另外再建立一个逆邻接链表, 使第i个链表表示以vi为头的所有的弧。 图7.6即为图G2的逆邻接表。 ,7.3 图的遍历和求图的连通分量,7.3.1图的建立 由上节知道, 可采用邻接矩阵或邻接链表作为图的存储结构。下面给出无向图的邻接矩阵的形式说明及其建立算法7.1。 算法7.1 typedef char vextype; /*顶点的数据类型 */ typedef struct
12、vextype vexsn+1; int arcsn+1n+1;ZK) graph;,void creatgraph(graph *ga) /*建立无向图*/ int i, j, k; for(i=1;ivexsi=getchar(); /*读入顶点信息 */ for (i=1; iarcsij=0; /*邻接矩阵初始化 */ for(k=1; karcsij=1; ga-arcsji=1; /*creatgraph*/,7.3.2 图的遍历 从图中某一顶点出发访遍其余顶点, 且使每一顶点仅被访问一次, 这一过程称为图的遍历。遍历图的基本方法有两种: 深度优先搜索和广度优先搜索。这两种方法都适
13、用于有向图和无向图。因为图的任一顶点都可能和其余顶点相邻接, 因此在遍历过程中, 可能会多次访问某个顶点。为了避免这种情况, 要记下每个已访问过的顶点, 一般可增设一个辅助数组visitedn, 每个visitedi的初值置为零。 一旦顶点vi被访问, 就将 visitedi置为1。 1. 连通图的深度优先搜索遍历,连通图的深度优先搜索遍历类似于树的先根遍历, 其基本思想如下: 假定图中某个顶点v1为出发点, 首先访问出发点然后选择一个v1的未访问的邻接点v2, 以v2为新的出发点继续进行深度优先搜索, 直至图中所有顶点都被访问过。 显然, 图的深度优先搜索是一个递归过程。 现以图7.7(a)
14、为例说明深度优先搜索过程。假定v1是出发点, 首先访问v1 。 因v1有两个邻接点v2 、 v3均未被访问过, 可以选择v2作为新的出发点,访问v2之后, 再找v2的未访问过的邻接点。同v2邻接的有v1 、 v4、 v5, 其中v1已被访问过, 而v4 、 v5尚未被访问过, 可以选择v4作为新的出发点。,重复上述搜索过程, 继续依次访问v8、 v5 。 访问v5之后, 由于与v5相邻的顶点均已被访问过, 搜索退回到v8 。 由于v8 、 v4 、 v2都是已被访问的邻接点, 所以搜索过程连续地从v v8退回到v4, 再退回到v2, 最后退回到v1 。 这时选择v1的未被访问过的邻接点v3,
15、继续往下搜索, 依次访问v3 、 v6、 v7 , 从而遍历了图中全部顶点。在这个过程中得到的顶点的访问序列为 v1 v2 v4 v8 v5 v3 v6 v7 因为深度优先搜索遍历是递归定义的, 故容易写出其递归算法。下面以邻接矩阵作为图的存储结构给出具体算法。 ,算法 7.2 int visitedMaxSize, n; /*访问标志数组 */ void dfstraverse(Graph G, int v) /*对图G作深度优先遍历 */ for(v=0;vG.vexnum; +v) visitedv=0; /*访问标志数组初始化 */ for (v=0;vG.vexnum; +v) if (!KG-*2visitedv) dfs(G, v); /*对尚未访问的顶点调用dfs*/ /*dfstraverse*/,void dfs(Graph G, int v) /*从第v个顶点出发递归地深度优先遍历图G */ visitedv=1; printf(“%d“, v); /*访问第v个
