We read every piece of feedback, and take your input very seriously.
To see all available qualifiers, see our documentation.
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
图是一种与树有些相似的数据结构。
那么图长什么样子呢?或者什么样的数据使用图来模拟更合适呢?
那么,什么是图呢?
图通常有什么特点呢?
顶点
边
相邻顶点
0 - 1
0 - 3
0 - 2
度
路径
v1
v2
vn
0 1 5 9
0 1 5 6 3 0
无向图
0 -> 1
1 -> 0
有向图
无权图
4 - 9
带权图
vertexes
adjList
class Graph { constructor() { this.vertexes = []; // 存储顶点 this.adjList = new Dictionay(); //存储边信息 } }
[]
// 添加顶点 addVertex(val) { // 添加点 this.vertexes.push(val) // 添加点的关系 采用邻接矩阵法 结构用Map this.adjList.set(val, []) }
// 添加边 addEdge(val1, val2) { // 添加边需要传入两个顶点, 因为边是两个顶点之间的边, 边不可能单独存在. // 这里实现的是无向图, 所以这里不考虑方向问题 this.adjList.get(val1).push(val2) this.adjList.get(val2).push(val1) }
The text was updated successfully, but these errors were encountered:
No branches or pull requests
什么是图?
图是一种与树有些相似的数据结构。
那么图长什么样子呢?或者什么样的数据使用图来模拟更合适呢?
那么,什么是图呢?
图通常有什么特点呢?
图的术语
术语
顶点
边
相邻顶点
0 - 1
是相邻的,0 - 3
是相邻的。0 - 2
是不相邻的。度
路径
v1
,v2
...,vn
的一个连续序列, 比如上图中0 1 5 9
就是一条路径。0 1 5 9
是一条简单路径。0 1 5 6 3 0
。无向图
0 - 1
之间有边,那么说明这条边可以保证0 -> 1
,也可以保证1 -> 0
。有向图
0 -> 1
,不能保证一定可以1 -> 0
,要根据方向来定。无权图和带权图
无权图
0 - 1
的边,比4 - 9
的边更远或者用的时间更长。带权图
现实建模
图的封装
创建图类
vertexes
用于存储所有的顶点,使用一个数组来保存。adjList
adj 是 adjoin 的缩写,邻接的意思。adjList 用于存储所有的边,这里采用邻接表的形式。添加方法
[]
,该数组用于存储顶点连接的所有的边.(回顾邻接表的实现方式)The text was updated successfully, but these errors were encountered: