《数据结构课件第五章图.pptx》由会员分享，可在线阅读，更多相关《数据结构课件第五章图.pptx（123页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本节内容图王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM图ACEB D树是N（N 0）个结点的有限集合，N=0 时，称为空树，这是一种特殊情况。在任意一棵非空树中应满足：1）有且仅有一个特定的称为根的结点。2）当N1 时，其余结点可分为m（m0）个互不相交的有限集合T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根结点的子树。F图G 由顶点集V 和边集E 组成，记为G=(V，E)V(G)表示图G 中顶点的有限非空集。用|V|表示图G 中顶点的个数，也称为图G 的阶。E(G)表示图G 中顶点之间的关系（边）集合。用|E|表示图G 中边的条数。Vertex Edge图
2、不可为空，一个图中就算是一条边都没有，也就是边集为空，但是顶点集一定不为空。王道考研/CSKAOYAN.COM图的基本概念AB CAB C无向图G2有向图G1G1=(V1，E1)V1=A，B，CE1=，G2=(V2，E2)V2=A，B，CE2=(A，B)，(A，C)，(B，C)王道考研/CSKAOYAN.COM图的基本概念AB CAB C王道考研/CSKAOYAN.COM图的基本概念AB CAB C对于n 个 顶点每个顶点都与其他n-1 个顶点有一条边，由于重复，所以一共有n*(n-1)/2 条边每个顶点都与其他n-1 个顶点有一条边，由于有方向不重复，所以一共有n*(n-1)条边王道考研/C
3、SKAOYAN.COM图的基本概念若有满足V(G)=V(G)的子图G，则为G 的生成子图ACA并非V 和E 的任何子集都能构成G 的子图，因为这样的子集可能不是图，也就是说，E 的子集中的某些边关联的顶点可能不在这个V 的子集中。G=(V，E)V=A，B，CE=，AB CG=(V，E)V=CE=，子图(a)子图(b)B王道考研/CSKAOYAN.COM图的基本概念ABDCEFG=(V，E)V=A，B，C，D，E，FE=(A，B)，(B，C)，(C，D)，(D，A)，(E，F)如果右图看成一个图则是不连通的找连通分量的方法：从选取一个顶点开始，以这个顶点作为一个子图，然后逐个添加与这个子图相连的
4、顶点和边直到所有相连的顶点都加入该子图结论1:如果一个图有n个顶点，并且有小于n-1 条边，则此图必是非连通图。王道考研/CSKAOYAN.COM图的基本概念AB CDG=(V，E)V=A，B，C，DE=，不连通AB CD强连通分量王道考研/CSKAOYAN.COM图的基本概念ABCDE F6 个顶点，7 条边ABCDE F6 个顶点，5 条边结论2:生成树去掉一条边则变成非连通图，加上一条边就会形成回路。王道考研/CSKAOYAN.COM图的基本概念AB C无向图AB C有向图无向图：有向图：TD(v)=ID(v)+OD(v)AB C有向树王道考研/CSKAOYAN.COM图的基本概念ABC
5、D1000A-B-C-D-A 路径长度为4A-B-C-A-D 和A-B-C-DB 和D 的距离为2王道考研/CSKAOYAN.COM图的基本概念本节内容图的存储结构王道考研/CSKAOYAN.COM王道考研/CSKAOYAN.COM图的存储结构图的存储结构相比线性表和树显得更复杂图中顶点没有次序之分图中边和顶点的数量任意王道考研/CSKAOYAN.COM邻接矩阵顶点：用一维数组来存储 边或弧：用二维数组来存储二维数组就是一维数组的拓展，相当于一维数组中每个元素也是一个一维数组。二维数组也叫做邻接矩阵a0a1a2a00 a01 a02a10a11 a12a20a21 a223*3 二维数组ABC
6、D顶点数组：A B C D边或弧数组：A B C DABCD0000aij=1 若(vi,vj)或 是E(G)中的边0 若(vi,vj)或 不是E(G)中的边1 1 11 11 1 11 0 10无向图的邻接矩阵是一个对称矩阵1.判定两个顶点是否有边2.求某个顶点的度3.找到某个顶点的所有邻接点因此可以只存储上半部分矩阵王道考研/CSKAOYAN.COM邻接矩阵ABCD顶点数组：A B C D边或弧数组：A B C DABCD00001 0 10 11 1 10 0 001.顶点的入度是顶点所在这一列的各数之和；出度是顶点所在这一行的各数之和。2.判定两个顶点是否有边3.找到某个顶点的所有邻接
7、点对于带权图(网)可以在矩阵中存储边的权值ABCD586732A B C DABCD00005867 3 2 1、带权边存储权值2、行和列相同结点权值为03、不存在的边权值为无限大王道考研/CSKAOYAN.COM邻接矩阵#define MaxVertexNum l00/顶点数目的最大值typedef char VertexType;/顶点的数据类型不同情况不一样typedef int EdgeType;/整数表示权值或者连通性typedef structVertexType VexMaxVertexNum;/顶点表EdgeType EdgeMaxVertexNumMaxVertexNum;/
8、邻接矩阵(二维数组)，边表int vexnum,arcnum;/图的当前顶点数和弧数MGraph;由于邻接矩阵基于二维数组，所以利用二维数组创建图的时间复杂度为O(n2)，其中n 为图的顶点数。所以当顶点数较多时，邻接矩阵的复杂度也会比较大。王道考研/CSKAOYAN.COM邻接表对于稀疏图(|E|远小于|V|2)ABCDA B C DABCD00001 0 00 00 0 00 0 00浪费存储空间顺序存储结构存在预先分配内存可能浪费的问题，按照经验会想到链式存储结构adbce fdataabcdef下标012345firstchild13524孩子表示法王道考研/CSKAOYAN.COM邻
9、接表dataABCD下标0123firstedge1ABCD2 30 20 1 30 2图中的顶点用一个一维数组存储。同时每个元素还要存储指向第一个邻接点的指针(链表的头指针)。存储顶点和头指针的表叫顶点表图中每个顶点的所有邻接点构成一个单链表。对于无向图，这个表称为该结点的边表，对于有向图称为该结点的出边表顶点表 边表王道考研/CSKAOYAN.COM邻接表dataABCD下标0123firstedge1ABCD2230注意是以顶点为弧尾需要设计两种结点结构类型：一是顶点表的顶点，二是单链表的结点#define MaxVertexNum 100/图中顶点数目的最大值typedef struc
10、t ArcNode/边表结点int adjvex;/该弧所指向的顶点的位置struct ArcNode*next;/指向下一条弧的指针ArcNode;typedef struct VNode/顶点表结点VertexType data;/顶点信息ArcNode*firstedge;/单链表头指针VNode,AdjListMaxVertexNum;/AdjList 是结构体数组类型typedef structAdjList vertices;/邻接表int vexnum,arcnum;/图的顶点数和弧数 ALGraph;/ALGraph 是以邻接表存储的图类型王道考研/CSKAOYAN.COM十字
11、链表dataABCD下标0123firstedge1ABCD2230注意是以顶点为弧尾有向图的邻接表关心了有向图的出边问题，我们通过有向图很容易找到顶点的出边比如从每个顶点表的firstedge 指针找到第一条边的顶点，再通过next 指针依次找到下一条边的顶点直到空指针。但是，如果要找到其他顶点到该顶点的边，或者说考虑一个顶点的入度问题，则需要遍历整个图。这是邻接表存储有向图的缺陷。王道考研/CSKAOYAN.COM十字链表十字链表是针对有向图的存储方式，对应于有向图中的每条弧有一个结点，对应于每个顶点也有一个结点data firstout firstin顶点结点headvextaillin
12、k headlinktailvex边表结点图中顶点的数据该顶点的入边表的头指针该顶点的出边表的头指针这条弧的弧尾(起点)所在顶点表下标这条弧的弧头(终点)所在顶点表下标指向弧头(终点)相同的下一条边指向弧尾(起点)相同的下一条边其实十字链表是在邻接表的基础上进行了优化。在十字链表中不仅包含了邻接表本身就包含的结点出度结点，而且还包含了入度结点的信息。王道考研/CSKAOYAN.COM十字链表ABCDABCD0 1下标0123入边表 出边表0 2弧尾弧头相同弧头相同弧尾1 2(A-B)(A-C)(B-C)2 1(C-B)3 0(D-A)2 3(C-D)该顶点的出边该顶点的入边十字链表的存储形式不唯一