《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS07-图》由会员分享，可在线阅读，更多相关《数据结构——C语言描述 教学课件 ppt 作者 王国钧 主编 唐国民 苏晓萍 马瑜 副主编 电子教案 DS07-图（74页珍藏版）》请在金锄头文库上搜索。
1、基本概念 图的存储结构 图的遍历 生成树 最短路径 拓扑排序,第7章 图,7.1 图的基本概念,图定义 图是由顶点集合(vertex)及顶点间的关系 集合组成的一种数据结构： Graph( V, E ) 其中 V = x | x 某个数据对象 是顶点的有穷 非空集合； E = (x, y) | x, y V 是顶点之间关系的有穷集合，也叫做边(edge)集 合。,有向图与无向图 若图G中的每条边都是有方向的，则称G为有向图。有向边也称为弧。若图G中的每条边都是没有方向的，则称G为无向图。 完全图 对有n个顶点的图，若为无向图且边数为n(n-1)/2，则称其为无向完全图；若为有向图且边数为n(n
2、-1) ，则称其为有向完全图。 邻接顶点 若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点，或称vi和vj相邻接，并称边（vi,vj）关联于顶点vi和vj，或称（vi,vj）与顶点vi和vj相关联。,顶点的度 一个顶点v的度是与它相关联的边的条数。记作TD(v)。,顶点 v 的入度 是以 v 为终点的有向边的条数, 记作 ID(v); 顶点 v 的出度是以 v 为始点的有向边的条数, 记作 OD(v)。,子图 设有两个图 G(V, E) 和 G(V, E)。若 V V 且 EE, 则称 图G 是 图G 的子图。,路径 在图 G(V, E) 中, 若存在一个顶点序列 vp1, vp2,
3、 , vpm，使得(vi, vp1)、(vp1, vp2)、 .、(vpm, vj)均属于E，则称顶点vi到vj存在一 条路径。若一条路径上除了vi 和vj 可以相同外， 其余顶点均不相同，则称此路径为一条简单路径 。起点和终点相同的路径称为简单回路或简单环。,图的连通 在无向图G中，若两个顶点vi和vj之间有 路径存在，则称vi 和vj 是连通的。若G中任意两 个顶点都是连通的，则称G为连通图。非连通图的 极大连通子图叫做连通分量。,强连通图与强连通分量 在有向图中, 若对于每一对顶点vi和vj, 都存在一条从vi到vj和从vj到vi的路径,则称此图是强连通图。非强连通图的极大强连通子图叫做
4、强连通分量。,权 某些图的边具有与它相关的数, 称之为权。这种带权图叫做网络。,1,2,3,5,6,8,7,4,A,B,D,C,E,10,7,9,6,6,7,12,3,15,16,60,30,45,35,80,40,75,权图,生成树 一个连通图的生成树是它的极小 连通子图，在n个顶点的情形下，有n-1条 边。,生成林 若G是一个不连通的无向图，G的每个连通分量都有一棵生成树，这些生成树构成G的生成森林。,7.2 图的存储结构,在图的邻接矩阵表示中，有一个记录各个顶点信息的顶点表，还有一个表示各个顶点之间关系的邻接矩阵。 设图 A = (V, E)是一个有 n 个顶点的图，则图的邻接矩阵是一个
5、二维数组 A .Edgenn，定义： 无向图的邻接矩阵是对称的，有向图的邻接矩阵可能是不对称的。,邻接矩阵 (Adjacency Matrix),在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。,网络的邻接矩阵,邻接矩阵表示法中图的类型定义： #define MAXSIZE 100 /*图的顶点个数*/ typedef int datatype; typedef struct datatype vexsMAXSIZE； /*顶点信息表*/ int edgesMAXS
6、IZE MAXSIZE；*邻接矩阵*/ int n，e ； /*顶点数和边数*/ graph；,2,1,4,3,5,无向图,B,A,D,C,E,有向图,2,1,5,3,4,6,20,30,50,40,70,80,有向权图,邻接矩阵表示法中无向网络的建立算法 void Create_Graph（graph *ga） int i，j ，k，w； printf (“请输入图的顶点数和边数：n“)； scanf (“%d“，&(ga-n)，& (ga-e)； printf (“请输入顶点信息(顶点编号)，建立顶点信息表：n“) ； for(i = 0；in；i+) scanf(“%c“,&(ga-ve
7、xsi)；/*输入顶点信息*/ for (i = 0；in；i+) /*邻接矩阵初始化*/ for (j = 0；jn；j+) ga-edgesij = 0； for (k = 0；ke；k+) /*读入边的顶点编号和权值，建立邻接矩阵*/ printf (“请输入第%d条边的顶点序号i，j和权值w：“,k+1)； scanf (“%d，%d，%d“，&i，&j，&w)； ga-edgesij = w； ga-edgesji = w； ,算法分析,该算法的执行时间是O(n+n2+e)，由于e n2，所以算法的时间复杂度为O(n2)。,邻接表 (Adjacency List),无向图的邻接表,表
8、结点,表头结点,data first vertex next,G5,每个链表的上边附设一个表头结点，在表头结点中，除了设有链域first用于指向链表中第一个结点之外，还设有存储顶点vi名或其它有关信息的数据域data 把同一个顶点发出的边链接在同一个边链表中，链表的每一个结点代表一条边，叫做表结点，结点中保存有与该边相关联的另一顶点的顶点下标 vertex 和指向同一链表中下一个表结点的指针 next。,有向图的邻接表和逆邻接表 在有向图的邻接表中，第 i 个边链表链接的边都是顶点 i 发出的边。也叫做出边表。 在有向图的逆邻接表中，第 i 个边链表链接的边都是进入顶点 i 的边。也叫做入边表
9、。,G6,邻接表,逆邻接表,邻接表的类型定义 #define nmax 100 /*假设顶点的最大数为100*/ typedef struct node *pointer； struct node /*表结点类型*/ int vertex ； struct node *next ； nnode； typedef struct /*表头结点类型，即顶点表结点类型*/ datatype data ； pointer first ；/*边表头指针*/ headtype ； typedef struct /*表头结点向量，即顶点表*/ headtype adlistnmax; int n，e ； lk
10、graph ；,无向图邻接表的建立算法 void creatqraph（Ikgraph *ga） /*建立无向图的邻接表*/ int i，j，e，k； pointer p； printf(“请输入顶点数：n”)； scanf (“%d”， ga-adlistj.first=p； /*将新表结点插入到顶点vj的边表头部*/ scanf (“n%d,%dn”， &i，&j )；/*读入一个顶点对号i和j*/ ga-e = e ； ,算法的时间复杂度是O（ne） 在邻接表的边链表中，各个表结点的链入顺序任意，视表结点输入次序而定。 设图中有 n 个顶点，e 条边，则用邻接表表示无向图时，需要 n 个
11、表头结点，2e 个表结点；用邻接表表示有向图时，若不考虑逆邻接表，只需 n 个表头结点，e 个表结点。 带权图的边结点中保存该边上的权值 cost。,网络 (带权图) 的邻接表,表结点,7.3 图的遍历性,从已给的连通图中某一顶点出发，沿着一些边访遍图中所有的顶点，且使每个顶点仅被访问一次，就叫做图的遍历 ( Graph Traversal )。 图中可能存在回路，且图的任一顶点都可能与其它顶点相通，在访问完某个顶点之后可能会沿着某些边又回到了曾经访问过的顶点。 为了避免重复访问，可设置一个标志顶点是否被访问过的辅助数组 visited ，它的初始状态为 0，在图的遍历过程中，一旦某一个顶点
12、i 被访问，就立即让 visited i 为 1，防止它被多次访问。,深度优先搜索DFS ( Depth First Search ),深度优先搜索的示例,DFS 在访问图中某一起始顶点 v 后，由 v 出发， 访问它的任一邻接顶点 w1；再从 w1 出发，访问与 w1邻接但还没有访问过的顶点 w2；然后再从 w2 出 发，进行类似的访问， 如此进行下去，直至到达 所有的邻接顶点都被访问过的顶点 u 为止。接着， 退回一步，退到前一次刚访问过的顶点，看是否还 有其它没有被访问的邻接顶点。如果有，则访问此 顶点，之后再从此顶点出发，进行与前述类似的访 问；如果没有，就再退回一步进行搜索。重复上述
13、 过程，直到连通图中所有顶点都被访问过为止。,深度优先搜索算法 void DFS（graph *g） /*按深度优先搜索法遍历图g*/ int i； for（i0；ig-n；i+ ） visidi = 0； /*初始化数组visid，使每个元素为0*/ /*标示图中的每个结点都未曾访问过*/ for（i= 0；in；i+） if（!visidi） DFSM(g，i)；/*调用函数DFSM，对图进行遍历*/ void DFSM（graph *g，int i ）/*邻接矩阵上进行DFS遍历*/ int j； printf（“深度优先遍历结点：%cn“ ，g-vexsi）； visidi=1; /*
14、假定g-vexsi为顶点的编号，然后变访问标志为1*/ for（j =0；jn；j+） if（g-edgesij = =1）！visidj） DFSM（g，j）； ,void DFSL（lkgraph *g，int n ）/*邻接表上进行DFS遍历*/ pointer p; int j； printf（“ %dn“ ，g- adlistn.data）； /*访问出发点，输出顶点数据*/ visidi=1; /*然后变访问标志为1*/ for（p = g-adlistn.first；p!=NULL； p = p-next） if（！visidp- vertex ） DFSL（g，p- verte
15、x ）； ,算法分析,图中有 n 个顶点，e 条边。 如果用邻接表表示图，沿链可以找到某个顶点 v 的所有邻接顶点 w。由于总共有 2e 个边结点，所以扫描边的时间为O(e)。而且对所有顶点递归访问1次，所以遍历图的时间复杂性为O(n+e)。 如果用邻接矩阵表示图，则查找每一个顶点的所有的边，所需时间为O(n)，则遍历图中所有的顶点所需的时间为O(n2)。,广度优先搜索BFS ( Breadth First Search ),广度优先搜索的示例,广度优先搜索过程 广度优先生成树,使用广度优先搜索在访问了起始顶点 v 之后，由 v 出发，依次访问 v 的各个未曾被访问过的邻接顶点 w1, w2, , wt，然后再顺序访问 w1, w2, , wt 的所有还未被访问过的邻接顶点。再从这些访问过的顶点出发，再访问它们的所有还未被访问过的邻接顶点， 如此做下去，直到图中所有顶点都被访问到为止。 广度优先搜索是一种分层的搜索过程，每向前走一步可能访问一批顶点，不像深度优先搜索那样有往回退的情况。因此，广度优先搜索不是一个递归的过程，其算法也不是递归的。,为了实现逐层访问，算法中使用了一个队列，以记忆正在访问的这一层和上一层的顶点，以便于向下一层访问。 与深度优先搜索过程一样，为避免重复访问，需要一个辅助数组 visited
