首页 26考研 在职考研 直播好课 大纲冲刺

新东方在线 > 考研 > 计算机 > 考研计算机复习指导 > 正文

扫码加入训练营

牢记核心词

学习得礼盒

2020考研计算机《数据结构(C语言版)》复习笔记(7)

2019-05-24 08:45:44来源：网络

　　2020年计算机考研复习已经开始，新东方在线在此整理了2020考研计算机《数据结构(C语言版)》复习笔记(7)，希望能帮助大家!

　　第七章 图知识点整理

　　图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的，即任意两个结点之间之间都可能相关。

　　图GraphG=(V，E)，V是顶点的有穷非空集合，E是顶点偶对的有穷集。

　　有向图Digraph：每条边有方向;无向图Undigraph：每条边没有方向。

　　有向完全图：具有n*(n-1)条边的有向图;无向完全图：具有n*(n-1)/2条边的无向图;

　　有根图：有一个顶点有路径到达其它顶点的有向图;简单路径：是经过顶点不同的路径;简单回路是开始和终端重的简单路径;

　　网络：是带权的图。

　　图的存储结构：

　　·邻接矩阵表示法：用一个n阶方阵来表示图的结构是唯一的，适合稠密图。

　　·无向图：邻接矩阵是对称的。

　　·有向图：行是出度，列是入度。

　　建立邻接矩阵算法的时间是O(n+n^2+e)，其时间复杂度为O(n^2)

　　·邻接表表示法：用顶点表和邻接表构成不是唯一的，适合稀疏图。

　　·顶点表结构 vertex | firstedge，指针域存放邻接表头指针。

　　·邻接表：用头指针确定。 ·无向图称边表;

　　·有向图又分出边表和逆邻接表;

　　·邻接表结点结构为 adjvex | next，

　　时间复杂度为O(n+e)。，空间复杂度为O(n+e)。。

　　图的遍历： ·深度优先遍历：借助于邻接矩阵的列。使用栈保存已访问结点。

　　·广度优先遍历：借助于邻接矩阵的行。使用队列保存已访问结点。

　　生成树的定义：若从图的某个顶点出发，可以系统地访问到图中所有顶点，则遍历时经过的边和图的所有顶点构成的子图称作该图的生成树。

　　最小生成树：图的生成树不唯一，从不同的顶点出发可得到不同的生成树，把权值最小的生成树称为最小生成树(MST)。

　　构造最小生成树的算法： ·Prim算法的时间复杂度为O(n^2)与边数无关适于稠密图。

　　·Kruskal算法的时间复杂度为O(lge)，主要取决于边数，较适合于稀疏图。

　　最短路径的算法：·Dijkstra算法，时间复杂度为O(n^2)。·类似于prim算法。

　　拓扑排序：是将有向无环图G中所有顶点排成一个线性序列，若∈E(G)，则在线性序列u在v之前，这种线性序列称为拓扑序列。

　　拓扑排序也有两种方法：

　　·无前趋的顶点优先，每次输出一个无前趋的结点并删去此结点及其出边，最后得到的序列即拓扑序列。

　　·无后继的结点优先：每次输出一个无后继的结点并删去此结点及其入边，最后得到的序列是逆拓扑序列。


本文关键字: 2020考研计算机

考研英语核心词汇营

背词+听课+练习+督学，学习得礼盒

更多资料

添加班主任领资料

添加考研班主任
免费领取考研历年真题等复习干货资料

  • 1.打开手机微信【扫一扫】，识别上方二维码；
  • 2.添加班主任，可领取学习资料。
更多>>
更多内容
看课程 MBA 优惠券 0元学 领资料

关注新东方在线考研服务号

获得21考研真题及答案解析

1. 打开手机微信【扫一扫】，识别上方二维码；
2.点击【关注公众号】，获取资料大礼包。

名师试听

历年考研真题及答案解析下载

英语一 英语二 政治 数学一 数学二 数学三 西医综合 教育综合 心理学综合
立即下载
近10年考研真题及答案免费下载
更多>>
更多公开课>>
更多>>
更多资料
我要
反馈 返回
首页
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10