福州网站运营,沐川移动网站建设,怎么建网站青州问枫,研发个app需要多少钱是什么 图是一种抽象的数据类型#xff0c;在图中的数据元素通常称作节点#xff0c;V是所以定点的集合#xff0c;E是所有边的集合
图的分类
有向图
如果两个订单v#xff0c;w#xff0c;只能由v向w#xff0c;而不能w向v#xff0c;那么我们就把何种情况叫做一个从…是什么 图是一种抽象的数据类型在图中的数据元素通常称作节点V是所以定点的集合E是所有边的集合
图的分类
有向图
如果两个订单vw只能由v向w而不能w向v那么我们就把何种情况叫做一个从v到w的有向边。v也被陈作初始点w也被称为终点。这种图也被称为有向图
无向图
如果v和w是没有顺序的从v到达w和从w到达v是完全相同的这种图就叫做无向图 常见的图表达方式
邻接矩阵
通过一个二维数组G[N][N]表示N个点到N-1编号通过邻街矩阵可以立即看到两个订单直接是否存在一条边 邻接表
存储方式如下 在javascript中永Object进行表示
const graph {A: [2, 3, 5],B: [2],C: [0, 1, 3],D: [0, 2],E: [6],F: [0, 6],G: [4, 5]
} 用数组进行表示 代码A
const graph {0: [1, 4],1: [2, 4],2: [2, 3],3: [],4: [3], } 常见的操作方式
深度优先遍历
广度优先遍历
数据如上面的代码A 深度优先
const visited new Set()
const dfs (n) {console.log(n)visited.add(n) // graph[n].forEach(c {if(!visited.has(c)){ //demo第一次遍历graph下的graph[1]和graph[4]dfs(c)}}) }dfs(0)
结果:0,1,2,3,4
这里只是恰巧是顺数如果把graph[0]改为[4,1]那结果会变成04312
广度优先
const visited new Set()
const dfs (n) {visited.add(n)const q [n]while(q.length){const n q.shift()console.log(n)graph[n].forEach(c {if(!visited.has(c)){q.push(c) visited.add(c)}})} }dfs(0)
结果
01 423
备注
上面的set是用来做去重的 使用场景 社交网络。
社交网络是典型的网络结构图可以用点来表达社交关系中的人用点与点之间的连接来表达人与人的关系。比如我们想要去表示谁认识谁、谁和谁沟通、谁能够影响谁等人与人之间的关系。一个具体的例子是在小红书上比如A 关注了 B 的小红书可以用 A 指向 B 的线来连接表示。这些人与人的社交信息可以用来去解释社交网络的信息流动。人与人之间的联系也定义了我们是谁。
交通网络。
交通网络也可以用图来表达。比如所有的城市可以用图的节点来表示城市间的交通渠道可以用边来表示。像最近大家关注的疫情封城措施也可以用数据结构来理解就是把交通网络图的一些边进行了阻隔。 互联网网站连接。
我们经常看到网站上会有指向其他网址的超链接。如果我们把互联网所有的网页定义成图的节点那么网页与网页之间的边就是这些链接了。如果大家熟悉 Google 经典的网页排名算法 PageRank就会知道搜索引擎正是用指向一个网页的引用数量去判断一个网页的质量。 第 13 讲用图来表达更为复杂的数据关系 · 数据结构精讲从原理到实战 · 看云
更多
https://www.cnblogs.com/jaxu/p/11338294.html
