考研交流、答疑解惑请加
22计算机考研交流群：
23计算机考研交流群：
哈喽，研友们，之前的知识点你学会了吗？点击回顾：考研计算机数据结构-二叉树的概念及特点每天一个经典知识点，希望同学们认真记忆呐，无论你是22考研还是23考研，相信都会有一些帮助~ps：临近考试，小编集合研究院老师为大家安排了一场冲刺模考—模考解析，模考试卷，戳码领取，无需费用，无需转发，下载查看！
（戳码领取）
好了，话不多说，下面就正式进入今天的知识点内容吧~正文（一）基本概念1.图图是比树更复杂的一种非线性数据结构。对于图来说，数据元素之间的关系是任意的，相关应用也更为广泛，比如交通图、通信网络图、工程图、计算机网络中的路由选择协议等。图（Graph）由数据元素和连续数据元素的边（弧）构成，图里的数据元素称为顶点（Vertex），连接这些顶点的称为边（Edge）或者弧（Arc）。图是由顶点集合和边集合组成，V是顶点的有穷非空集合；VR是两个顶点之间的关系的集合。若n,w∈VR，则n,w表示从n到w的一条弧。2.有向图n为弧尾（Tail）或初始点（Initialnode），称w为弧头（Head）或终端点（Terminalnode），边有方向的图称为有向图（DirectedGraph）。连接边的两个顶点的线必须有顺序要求，V1到V2的边可以用V1，V2表示，V2到V1的边可以用V2，V1表示。3.无向图边没有方向的图称为无向图（UndirectedGraph）,连接边的两个顶点的线没有顺序要求，对于连接V1和V2两个顶点之间的边，可以用（V1，V2）表示，也可以用（V2，V1）表示。(a)有向图G1(b)无向图G2图的举例4.顶点的度、入度和出度对于无向图G=(V，{E})，如果边(n，n)∈E，则称顶点n和n互为邻接点（Adjacent）。边(n，n)依附（Incident）于顶点n和n，或者说(n，n)和顶点n和n相关联，顶点n的度是指依附于该顶点的边的条数，记为TD(n)。有：对于有向图G=(V，{A})，如果弧n，n∈A，则称顶点n邻接到顶点n，顶点n邻接自顶点n。以顶点n为头的弧的数目称为n的入度（InDegree），记为ID(n)；以n为尾的弧的数目称为n的出度（Outdegree），记为OD(n)；顶点n的度为TD(n)=ID(n)+OD(n)。有：5.完全图用n表示图中顶点数目，用e表示边或弧的数目。不考虑顶点到其自身的弧或边，即若（ni，nj）∈VR，则ni1nj，那么，对于无向图，e的取值范围是0到n*(n-1)/2。有n*(n-1)/2条边的无向图称为无向完全图（Completedgraph）。对于有向图，e的取值范围是0到n(n-1)。具有n(n-1)条弧的有向图称为有向完全图。6.稀疏图、稠密图有很少条边或弧（如enlogn）的图称为稀疏图（Sparsegraph），反之称为稠密图（Densegraph）。7.子图若图G=(V，{E})和G=(V，{E})，如果VíV且EíE，则称G为G的子图（Subgraph）。8.权、网与图的边或弧相关的数叫做权（Weight）。带权的图通常称为网（Network）。9.路径图G=(V，{E})中从顶点n到顶点n的路径（Path）是一个顶点序列。10.路径长度路径长度是路径上的边或弧的数目。11.回路第一个顶点和最后一个顶点相同的路径称为回路或环（Cycle）。12.简单路径、简单回路序列中顶点不重复出现的路径称为简单路径。除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简单环。13.连通图、连通分量在无向图G中，如果从顶点n到顶点n有路径，则称v和n是连通的。图中任意两个顶点ni、nj∈V，ni和nj都是连通的，则称G是连通图（ConnectedGraph）。否则就是非连通的。所谓连通分量（ConnectedComponent），指的是无向图中的极大连通子图。一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-l条边。(a)无向图G3(b)G3的3个连通分量无向图及其连通分量14.强连通图、强连通分量在有向图G中，如果对于每一对ni、nj∈V，ni≠nj，从ni到nj和从nj到ni都存在路径，则称G是强连通图。有向图中的极大强连通子图称做有向图的强连通分量。G1的两个强联通分量（二）特点1.图的存储结构：邻接矩阵（适用于稠密图）、邻接表（适用于稀疏图）、逆邻接表、十字链表、邻接多重表；2.图的遍历：深度优先遍历（DFS）、广度优先遍历（BFS）；3.最小生成树：普里姆（Prim）算法、克鲁斯卡尔（Kruskal）算法；4.最短路径：迪杰斯特拉（Dijkstra）算法、弗洛伊德（Floyd）算法。以上就是今天分享的全部内容啦，同学们想要了解其他内容的话就在评论区里留言吧~
你的过去我来不及参与你的未来我不会再错过11.11考研好课，强势上线多模式福利等你来拿中公教育相伴朝夕（轻戳
本文编辑：佚名
转载请注明出地址 http://www.jiubiyinga.com/xwgj/13909.html
