数据结构专升本资料第六周.docx
《数据结构专升本资料第六周.docx》由会员分享，可在线阅读，更多相关《数据结构专升本资料第六周.docx（10页珍藏版）》请在冰点文库上搜索。
数据结构专升本资料第六周
第七章图
7.1图的定义和术语
一、三种数据结构比较
线性表：
数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继；
树形结构：
数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素相关，但只能和上一层中一个元素相关；
图形结构：
结点之间的关系可以是任意的，图中任意两个元素之间都可能相关。
二、图的基本术语
图（Graph）：
图G由两个集合V和E组成，记为G=（V,E），这里，V是顶点的有穷非空集合，E是边（或弧）的集合，而边（或弧）是V中顶点的偶对。
顶点（Vertex）：
图中的结点又称为顶点。
边（Edge）：
相关顶点的偶对称为边。
有向图（Digraph）：
若图G中的每条边都是有方向的，则称G为有向图。
弧（Arc）：
又称为有向边。
在有向图中，一条有向边是由两个顶点组成的有序对，有序对通常用尖括号表示。
弧尾（Tail）：
边的始点。
弧头（Head）：
边的终点。
无向图（Undigraph）：
若图G中的每条边都是没有方向的，则称G为无向图。
无向完全图（UndirectedCompleteGraph）：
恰好有n（n-1）/2的无向图。
有向完全图（DirectedCompleteGraph）：
恰好有n（n-1）条弧的有向图。
邻接点（Adjacent）：
若（vi,vj）是一条无向边，则称顶点vi和vj互为邻接点。
度（Degree）：
无向图中顶点v的度是关联于该顶点的边的数目，记为TD（v）。
入度（Indegree）：
若G为有向图，则把以顶点v为终点的边的数目，称为v的入度，记为ID（v）。
出度（Outdegree）：
若G为有向图，则把以顶点v为始点的边的数目，称为v的出度，记为OD（v）。
对于有向图：
TD（v）=ID（v）+OD（v）
子图（Subgraph）：
设G=（V,E）是一个图，若E'是E的子集，V'是V的子集，使得E'中的边仅与V'中顶点相关联，则图G'=（V',E'）称为图G的子图。
路径（Path）：
无向图G=（V,E）中从顶点v到顶点v'的路径是一个顶点序列（v=vi0,vi1,…,vin=v'），其中（vij-1,vij）∈E，1≤j≤n。
有向图G=（V,E）中从顶点v到顶点v'的路径是一个顶点序列（v=vi0,vi1,…,vin=v'），其中〈vij-1,vij〉∈E，1≤j≤n。
简单路径：
序列中顶点不重复出现的路径。
环（Cycle）：
又称回路，第一个顶点和最后一个顶点相同的路径。
简单回路：
又称简单环，除了第一个顶点和最后一个顶点外，其余顶点不重复的回路。
连通：
在无向图G中，如果从顶点v到顶点v'有路径，则称v和v'是连通的。
连通图（ConnectedGraph）：
如果对于图中的任意两个顶点vi、vj∈V，vi和vj都是连通的，则称该图为连通图。
连通分量（ConnectedComponent）：
无向图中的极大连通子图。
强连通图：
在有向图G中，如果对于每一对vi，vj∈V，vi≠vj，从vi到vj和从vj到vi都存在路径，则称G是强连通图。
强连通分量：
有向图中的极大连通子图。
生成树（SpanningTree）：
含有连通图的全部顶点的一个极小连通子图。
一棵有n个顶点的生成树有且仅有n-1条边。
如果一个图有n个顶点和小于n-1条边，则是非连通图。
如果多于n-1条边，则一定有环。
网络（Network）：
若将图的每条边都赋上一个权，则称这种带权图为网络。
无向图和有向图对照表
7.2图的存储结构
一、邻接矩阵表示法：
邻接矩阵（AdjacencyMatrix）：
是表示顶点之间相邻关系的矩阵。
设G=（V,E）是一个图，其中V={v1,v2,…,vn}。
G的邻接矩阵是一个具有下列性质的n阶方阵：
特点
●无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定对称。
因此，用邻接矩阵来表示一个具有n个顶点的有向图时需要n2个单元来存储邻接矩阵；对有n个顶点的无向图则只存入上（下）三角阵，故只需n（n+1）/2个单元。
●无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
●有向图邻接矩阵中第i行非零元素的个数为第i个顶点的出度，第i列非零元素的个数为第i个顶点的入度，第i个顶点的度为第i行与第i列非零元素个数之和。
●用邻接矩阵表示图，很容易确定图中任意两个顶点是否有边相连。
二、邻接表表示法
邻接表（AdjacencyList）：
是图的一种链式存储结构。
在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对有向图是以顶点vi为尾的弧）。
邻接表由两部分构成：
表头结点、表结点组成的单链表。
邻接表的表示意义为：
对于图G=（V,E），若（i,j）∈E，则第i个表头结点的单链表上有一个adjvex为j的表结点。
无向图的邻接表称为边表，有向图的邻接表称为出边表，邻接表的表头向量称为顶点表。
逆邻接表在有向图中，对每个顶点vi建立一个链接以vi为头的弧表。
逆邻接表在形式上由两部分构成：
表头结点、表结点组成的单链表。
表头结点与邻接表完全一样，但表结点组成的单链表是不同的。
逆邻接表的表示意义为：
对于图G=（V,E），若＜i,j＞∈E，则第j个表头结点的单链表上有一个adjvex为i的表结头。
稀疏图（Sparsegraph）：
有很少条边或弧（如e＜nlogn）的图。
稠密图（Densegraph）：
边很多的图。
相比之下，从存储空间角度看，邻接表更适合于表示稀疏图而邻接矩阵适合于表示稠密图
一个图的邻接矩阵表示是唯一的，但其邻接表表示不唯一，各边表结点的链接次序取决于建立邻接表的算法和边的输入次序。
7.3图的遍历
图的遍历（TraversingGraph）：
从图中某一顶点出发访遍图中其余顶点，且使每一个顶点仅被访问一次。
图的遍历有两种方法：
深度优先搜索和广度优先搜索。
一、深度优先遍历（Depth-FirstTraversal）：
首先访问出发点v，并将其标记为已访问过；然后依次从v出发搜索v的每个邻接点w，若w未曾访问过，则以w为新的出发点继续进行深度优先遍历，直至图中所有和源点v有路径相通的顶点（亦称为从源点可达的顶点）均已被访问为止；若此时图中仍有未访问的顶点，则另选一个尚未访问的顶点作为新的源点重复上述过程，直至图中所有顶点均已被访问为止。
深度优先搜索（Depth-FirstSearch）：
深度优先遍历定义是递归的，其特点是尽可能先对纵深方向进行搜索，故这种搜索方法称为深度优先搜索。
深度优先遍历序列：
对图进行深度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的深度优先遍历序列，或简称为DFS序列。
二、广度优先遍历（Breadth-FirstTraversat）
从图中某个顶点v出发，在访问了v之后依次访问v的各个未曾访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，并使“先被访问的顶点的邻接点”先于“后被访问的顶点的邻接点”被访问，直至图中所有已被访问的顶点的邻接点都被访问到。
若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。
广度优先搜索（Breadth-FirstSearch）：
广度优先遍历过程中所使用的搜索方法，其特点是尽可能先对横向进行搜索，故称其为广度优先搜索。
广度优先遍历序列：
对图进行广度优先遍历时，按访问顶点的先后次序得到的顶点序列称为该图的广度优先遍历序列，或简称为BFS序列
7.4生成树和最小生成树
一、生成树（SpanningTree）
从连通图的任何一个顶点出发进行遍历，遍历过程中经过的边加上图的所有顶点构成的子图称为图的生成树。
深度优先生成树：
由深度优先搜索得到的生成树，简称为DFS生成树。
广度优先生成树：
由广度优先搜索得到的生成树，简称为BFS生成树。
在对无向图进行遍历时，对于连通图，仅需从图中任一顶点出发，进行深度优先搜索或广度优先搜索，便可访问到图中所有顶点。
对非连通图，则需从多个顶点出发进行搜索，而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。
二、最小生成树（MinimumSpanningTree）
各边权的总和最小的生成树。
MST性质：
假设N=（V,E）是一个连通网，U是顶点集V的一个非空子集。
若（U,V）是一条具有最小权值的边，其中u∈U，v∈V-U，则必存在一棵包含边（U,V）的最小生成树。
普里姆（Prim）算法
基本思想：
设G=（V,E）是连通网，顶点集V={v1,v2,…,vn}，T=（U,TE）是欲构造的最小生成树。
任选V中一顶点（不妨为v1）。
初始化U={v1}，TE=Φ。
重复下列操作：
在所有u∈U中，v∈V-U的边（u,v）∈E中，选择一条权值最小的边（u,v）并入TE，同时将v并入U，直到U=V为止，这时产生的TE中具有n-1条边，则上述过程求得的T=（U,TE）是G的一棵最小生成树。
普里姆算法构造最小生成树的过程
普里姆算法的时间复杂度为O（n2），与图中边数无关，该算法适合于稠密图。
P95例子
克鲁斯卡尔算法（Kruskal）
基本思想：
设G=（V,E）是连通网，顶点集V={v1,v2,…,vn}，T=（U,TE）是欲构造的最小生成树,E（T）是其边集！
在E（T）内选取V最小的值，依次的进行下去，直到所有的点全部的连接！
P96例子
升级会员 