考研论坛

 找回密码
 立即注册
查看: 560|回复: 0

2019考研计算机:数据结构知识点整理(7)

[复制链接]

33万

主题

33万

帖子

100万

积分

论坛元老

Rank: 8Rank: 8

积分
1007237
发表于 2018-12-24 19:58:36 | 显示全部楼层 |阅读模式
下面是新东方在线整理的2019考研计算机专业课资料:数据结构的知识点整理,请参考:
      第七章 图知识点整理
    图的逻辑结构特征就是其结点(顶点)的前趋和后继的个数都是没有限制的,即任意两个结点之间之间都可能相关。
    图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之前,这种线性序列称为拓扑序列。
    拓扑排序也有两种方法:
    ·无前趋的顶点优先,每次输出一个无前趋的结点并删去此结点及其出边,最后得到的序列即拓扑序列。
    ·无后继的结点优先:每次输出一个无后继的结点并删去此结点及其入边,最后得到的序列是逆拓扑序列。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|新都网 ( 京ICP备09058993号 )

GMT+8, 2024-3-29 04:18 , Processed in 0.072873 second(s), 13 queries , WinCache On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表