数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源07图

1、第7章 图,图是一种比线性表和树更加复杂的数据结构。在线性表中，数据元素之间呈现一种线性关系，即每个元素只有一个直接前驱和一个直接后继；在树结构中，结点之间是一种层次关系，即每个结点只有一个直接前驱，但可有多个直接后继；而在图结构中，每个结点既可以有多个直接前驱，也可以有多个直接后继 图结构可以描述各种复杂的数据对象，图的应用已渗入到诸如语言学、逻辑学、物理、化学、电讯工程、计算机科学以及数学的其它分支中 本章首先介绍图的概念，然后讨论图在计算机中的表示方法以及有关图的几个典型应用及相应的算法,图的基本概念 图的存储结构 图的遍历 图的最小生成树 最短路径 有向无环图及其应用,51 图的基本概念,图的定义 图是由顶点集合(vertex)及顶点间的关系集合组成的一种数据结构： Graph( V, E ) 其中 V 是顶点的有穷非空集合； E 是顶点之间关系的有穷集合，也叫做边(edge)集合,无向图 在无向图中,顶点对(vi , vj )是无序的， (vi,vj )表示顶点vi和vj间相连的边;,有向图 在有向图中,顶点对是有序的，表示从顶点vi到顶点vj的一条弧,并称vi为弧尾（或初始

2、点），称vj为弧头（或终端点）,图的基本术语,邻接点、相关边 对于无向图G=(V, E)，若边(vi , vj)E，则称vi和vj互为邻接点(Adjacent)，边(vi , vj)则是与顶点vi和vj相关联的边。 对于有向图G=(V, A)，若弧A，则称顶点vi邻接到顶点vj，顶点vj邻接自顶点vi，弧和顶点vi、vj相关联,在下面的讨论中，不考虑顶点到其自身的边或弧，也不允许一条边或弧在图中重复出现。同时用n表示图中顶点的数目，用e表示边或弧的数目,完全图 若有 n 个顶点的无向图有 n(n-1)/2 条边, 则此图为完全无向图。有 n 个顶点的有向图有n(n-1) 条边, 则此图为完全有向图,子图 设有两个图 G(V, E) 和 G(V, E),若 V V 且 EE, 则称 图G是 图G 的子图,顶点的度（Degree） 图中和vi相关联的边的数目，记为TD(vi)。在有向图中, 顶点的度等于该顶点的入度与出度之和 顶点 vi的入度 指以vi为头的弧的数目，记为ID(vi) 顶点vi的出度(OutDegree) 指以vi为尾的弧的数目，记为OD(vi) 有n个顶点，e条边或弧的图

3、，满足如下关系,路径 在图G(V, E)中,若从顶点vi 出发,沿一些边(或弧)经过一些顶点vp1, vp2, , vpm 到达顶点vj 。则称顶点序列(vi , vp1 , vp2 , . , vpm , vj )为从顶点vi 到顶点vj 的路径 简单路径 路径上各顶点 v1,v2,.,vm 均不互相重复的路径 路径长度 路径上边(或弧)的条数 回路 若路径上第一个顶点 v1 与最后一个顶点vm 重合, 则称这样的路径为回路或环,连通 若从顶点vi到顶点vj（ij）有路径，则称vi和vj是连通的。 连通图与连通分量 在无向图中, 若从顶点v1到顶点v2有路径, 则称顶点v1与v2是连通的。如果图中任意一对顶点都是连通的, 则称此图是连通图。非连通图的极大连通子图叫做连通分量 强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径, 则称此图是强连通图。非强连通图的极大强连通子图叫做强连通分量,权、网 图的每条边或弧上，标上具有某种含义的数值，这种与图的边相关的数值称为权（Weight）。带权的图称为网（Network）,52 图的

4、存储结构,图的存储结构或表示方式比较多，在选择图的存储结构时，通常取决于具体的应用和所定义的操作。下面介绍两种基本的存储结构，即邻接矩阵表示法和邻接表。,邻接矩阵(Adjacency Matrix)表示法,在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵 设图 G= (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个二维数组 G.arcsnn，定义:,邻接矩阵表示：,邻接矩阵表示：,网络的邻接矩阵,若G是网，则：,Wij表示边上的权值； 代表一个计算机允许的、大于所有边上权值的正整数,邻接矩阵表示：,无向图的邻接矩阵是对称的，有向图的邻接矩阵不一定是对称的 在无向图中, 统计第 i 行(列)中非零元素的个数可得顶点vi的度 在有向图中, 统计第i 行中非零元素的个数可得顶点vi 的出度，统计第i 列中非零元素的个数可得顶点vi的入度 邻接矩阵的行表示顶点的出边，列表示顶点的入边，因此从邻接矩阵很容易确定图中任意两个顶点间是否有边（或弧）相连 测试图中边（或弧）的数目时，则必须按行、列逐次检测,图的邻接矩阵表示法的特点,图的邻接矩阵表示

5、的存储结构定义,#define VEX_NUM 10 /*顶点数目*/ typedef char Vextype; /*顶点类型*/ typedef struct Vextype vexsVEX_NUM; /*顶点表*/ int arcsVEX_NUMVEX_NUM; /*邻接矩阵*/ Mgraph;,建立无向图的邻接矩阵算法,/*算法5.1 建立无向图的邻接矩阵G ,e为边的数目*/ void creat _Mgraph( Mgraph *G,int e) for (i=0;ivexsi); /*输入顶点信息*/ for (i=0;iarcsij=0; for(k=0;karcsij=1; G-arcsji=1; ,邻接表(Adjacency List),图的邻接表是一种顺序分配和链式分配相结合的存储结构 在邻接表中，对图中的每个顶点建立一个单链表,链表的每一个结点代表一条边,叫做表结点,结点中保存与该边相关联的另一顶点的顶点下标 adjvex 和指向同一链表中下一个表结点的指针 nextarc 第i个单链表中的结点表示依附于顶点vi 的所有的边（对有向图是以顶点vi 为弧尾的弧）

6、每个链表上附设一个表头结点,结点中存储顶点vi 的有关信息data 和指向链表表中第一个表结点的指针firstarc,每个链表上附设一个表头结点 链域（firstarc） 指向表中第一个结点 数据域（data） 存储顶点vi的名称或者其他有关信息,邻接点域(adjvex) 与顶点vi邻接的顶点在图中的序号 链域(nextarc) 依附于顶点vi的下一条边或弧所对应的结点权值域(weight) 边或弧所代表的权值,图的邻接表存储结构定义 #define VEX_NUM 10 /*顶点数目*/ typedef char Vextype; /*顶点类型*/ typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; /*表结点*/ typedef struct vnode Vextype data; ArcNode *firstarc; VNode; /* 头结点*/ typedef VNode ALgraphVEX_NUM; /*图的邻接链表*/,无向图G1的邻接表,图的邻接表的特点,设图中有 n 个顶点，e 条

7、边，则用邻接表表示无向图时，需要 n 个头结点，2e 个表结点； 用邻接表表示有向图时，只需n个头结点，e 个表结点 在无向图中, 统计第i 个链表中表结点的个数可得顶点 vi 的度 在有向图的邻接表中, 统计第i 个链表中表结点的个数可得顶点vi 的出度 在有向图的邻接表中求 vi 的入度，必须扫描整个邻接表，统计顶点域的值为 i 的表结点的数目 在有向图的逆邻接表中, 统计第i 个链表中表结点的个数可得顶点 vi 的入度,/*算法5.2 建立有向图的邻接表G ，e为弧的数目*/ void creat_ALgraph( ALgraph G,int e) for(i=0;i的顶点序号i,j*/ p=(ArcNode *)malloc(sizeof(ArcNode); p-adjvex=j; p-nextarc=Gi.firstarc; Gi.firstarc=p; ,思考：算法5.2作如何修改可建立无向图的邻接表？,53 图的遍历,图的遍历：从图中某一顶点出发遍历图中其余顶点，且使每一顶点仅被访问一次 遍历图的基本方法： 深度优先搜索DFS( Depth First Search )

8、广度优先搜索BFS ( Breadth First Search ) 图的任一顶点都可能和其余顶点相邻接,且可能存在回路，因此在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点,为了避免重复访问, 可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点 vi 被访问，就立即让 visited i 置为 1，防止它被多次访问,连通图的深度优先搜索遍历DFS ( Depth First Search ),基本思想 先访问图中某一起始顶点v ，然后由v 出发，访问它的任一邻接顶点 w1 ；再从w1 出发，访问与w1 邻接但还没有访问过的顶点w2 ；然后再从w2 出发，进行类似的访问， 如此进行下去，直至到达所有的邻接顶点都被访问过的顶点u 为止。接着，退回一步，退到前一次刚访问过的顶点，看是否还有其它没有被访问的邻接顶点。如果有，则访问此顶点，之后再从此顶点出发，进行与前述类似的访问；如果没有，就再退回一步进行搜索。重复上述过程，直到连通图中所有顶点都被访问过为止。,深度优先搜索遍历过程示例,5,8,深度优先搜索遍历序列为

9、v0、 v1、 v3、 v7、 v4、 v2、 v6、 v5,连通图的广度优先搜索遍历类似于树的先根遍历,/*算法7.3 从第i个顶点出发深度优先遍历以邻接矩阵表示的图G*/ int visitedNAX_VEX=0; void Dfs_m( Mgraph *G,int i) printf(“%3c“,G-vexsi); /*访问顶点vi*/ visitedi=1; for (j=0;jarcsij=1) ,/*算法7.4 从第i个顶点出发深度优先遍历以邻接表表示的图G*/ int visitedVEX_NUM=0; void Dfs_L(ALgraph G,int i) printf(“%3c“,Gi.data); /*访问顶点vi*/ visitedi=1; p=Gi.firstarc; while (p!=NULL) if(visitedp-adjvex=0) Dfs_L(G,p-adjvex); p=p-nextarc; ,算法分析,设图中有 n 个顶点，e 条边 如果用邻接矩阵表示图，搜索一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2) 如果用邻接表表示图，沿开始顶点v 的 firstarc 链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e),连通图的广度优先搜索遍历BFS ( Breadth First Search ),基本思想:从图中某个顶点v 出发，在访问了v之后，依次访问v 的各个未曾访问过的邻接点；然后分别从这些邻接点出发，依次访问它们的未曾访问过的邻接点，直至所有顶点都被访问过 连通图的广度优先搜索遍历类似于树的按层次遍历,广度优先搜索遍历过程示例,广度优先搜索遍历序列为 v0、 v1、 v2、 v3、 v4、 v5、 v6、 v7,广度优先搜索是一种分层的搜索

《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源07图》由会员E****分享，可在线阅读，更多相关《数据结构与算法——C语言和Java语言描述 ppt及答案和其他资源07图》请在金锄头文库上搜索。