图Graph

  • A+
所属分类:算法与数据结构

图Graph

图的基本概念

顶点(vertex) 边(edge) 度 入度 出度 有向图 无向图 带权图

储存方式

矩阵 稀疏图 浪费空间

邻接表 节省空间,但查找两个顶点是否相邻比较耗费时间。如果链太长,可以用跳表 平衡二叉查找树 散列表来提高效率。

暴力搜索算法

即广度优先算法(breath-first-search, BFS)和深度优先算法(depth-first-search, DFS)

代码:

 

复杂度分析:

BFS:如果目标顶点离初始顶点很远,那么需要遍历所有的顶点,每个顶点都要进出一遍队列,每个边也都会被访问一次,时间复杂度为O(V+E),对于联通图来说,图的所有顶点都是连通的,边的数量大于等于顶点的数量减1,所以可以写成O(E)。需要存储visited, prev 数组和queue,空间复杂度为O(V)。

DFS:每条边最多访问2次(递归的入栈 出栈),时间复杂度为O(E),需要存储visited, prev 数组,空间复杂度为O(V)

LTXU
  • 版权声明:本站原创文章,于2019年8月27日23:06:58,由 发表,共 428 字。
  • 转载请注明:图Graph | AICSDN

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: