图-基础概念

是什么

图是一种抽象的数据类型，在图中的数据元素通常称作节点，V是所以定点的集合，E是所有边的集合

图的分类

有向图

如果两个订单v，w，只能由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]那结果会变成0，4，3，1，2

广度优先

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)

结果

0，1， 4，2，3

备注

上面的set是用来做去重的 

使用场景

社交网络。

社交网络是典型的网络结构，图可以用点来表达社交关系中的人，用点与点之间的连接来表达人与人的关系。比如我们想要去表示谁认识谁、谁和谁沟通、谁能够影响谁等人与人之间的关系。一个具体的例子是在小红书上，比如，A 关注了 B 的小红书，可以用 A 指向 B 的线来连接表示。这些人与人的社交信息，可以用来去解释社交网络的信息流动。人与人之间的联系也定义了我们是谁。

交通网络。

交通网络也可以用图来表达。比如所有的城市可以用图的节点来表示，城市间的交通渠道可以用边来表示。像最近大家关注的疫情封城措施，也可以用数据结构来理解，就是把交通网络图的一些边进行了阻隔。
互联网网站连接。

我们经常看到网站上会有指向其他网址的超链接。如果我们把互联网所有的网页定义成图的节点，那么网页与网页之间的边就是这些链接了。如果大家熟悉 Google 经典的网页排名算法 PageRank，就会知道，搜索引擎正是用指向一个网页的引用数量去判断一个网页的质量。

第 13 讲：用图来表达更为复杂的数据关系 · 数据结构精讲：从原理到实战 · 看云

更多

https://www.cnblogs.com/jaxu/p/11338294.html