文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

面试官:说说你对堆的理解?如何实现?应用场景?

2024-12-02 21:05

关注

一、是什么

在计算机科学中,图是一种抽象的数据类型,在图中的数据元素通常称为结点,V是所有顶点的集合,E是所有边的集合

如果两个顶点v,w,只能由v向w,而不能由w向v,那么我们就把这种情况叫做一个从 v 到 w 的有向边。v也被称做初始点,w也被称为终点。这种图就被称做有向图

如果v和w是没有顺序的,从v到达w和从w到达v是完全相同的,这种图就被称为无向图

图的结构比较复杂,任意两个顶点之间都可能存在联系,因此无法以数据元素在存储区中的物理位置来表示元素之间的关系

常见表达图的方式有如下:

邻接矩阵

通过使用一个二维数组G[N][N]进行表示N个点到N-1编号,通过邻接矩阵可以立刻看出两顶点之间是否存在一条边,只需要检查邻接矩阵行i和列j是否是非零值,对于无向图,邻接矩阵是对称的

邻接表

存储方式如下图所示:

在javascript中,可以使用Object进行表示,如下:

  1. const graph = { 
  2.   A: [2, 3, 5], 
  3.   B: [2], 
  4.   C: [0, 1, 3], 
  5.   D: [0, 2], 
  6.   E: [6], 
  7.   F: [0, 6], 
  8.   G: [4, 5] 

图的数据结构还可能包含和每条边相关联的数值(edge value),例如一个标号或一个数值(即权重,weight;表示花费、容量、长度等)

二、操作

关于图的操作常见的有:

首先构建一个图的邻接矩阵表示,如下面的图:

用代码表示则如下:

  1. const graph = { 
  2.   0: [1, 4], 
  3.   1: [2, 4], 
  4.   2: [2, 3], 
  5.   3: [], 
  6.   4: [3], 

深度优先遍历

也就是尽可能的往深处的搜索图的分支

实现思路是,首先应该确定一个根节点,然后对根节点的没访问过的相邻节点进行深度优先遍历

确定以 0 为根节点,然后进行深度遍历,然后遍历1,接着遍历 2,然后3,此时完成一条分支0 - 1- 2- 3的遍历,换一条分支,也就是4,4后面因为3已经遍历过了,所以就不访问了

用代码表示则如下:

  1. const visited = new Set() 
  2. const dfs = (n) => { 
  3.   console.log(n) 
  4.   visited.add(n) // 访问过添加记录 
  5.   graph[n].forEach(c => { 
  6.     if(!visited.has(c)){ // 判断是否访问呢过 
  7.       dfs(c) 
  8.     } 
  9.   }) 

广度优先遍历

先访问离根节点最近的节点,然后进行入队操作,解决思路如下:

用代码标识则如下:

  1. const visited = new Set() 
  2. const dfs = (n) => { 
  3.   visited.add(n) 
  4.   const q = [n] 
  5.   while(q.length){ 
  6.     const n = q.shift() 
  7.     console.log(n) 
  8.     graph[n].forEach(c => { 
  9.       if(!visited.has(c)){ 
  10.         q.push(c)   
  11.         visited.add(c) 
  12.       } 
  13.     }) 
  14.   } 

三、总结

通过上面的初步了解,可以看到图就是由顶点的有穷非空集合和顶点之间的边组成的集合,分成了无向图与有向图

图的表达形式可以分成邻接矩阵和邻接表两种形式,在javascript中,则可以通过二维数组和对象的形式进行表达

图实际是很复杂的,后续还可以延伸出无向图和带权图,对应如下图所示:

参考文献

https://zh.wikipedia.org/wiki/%E5%9B%BE_(%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84)

 

https://www.kancloud.cn/imnotdown1019/java_core_full/2159607

 

来源:JS每日一题 内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯