实现图
前言
图为非线性数据结构
图结构的特点
- 一组顶点 用V(vertex)表示顶点的集合
- 一组边 用E(edge)表示边的集合 边是顶点和顶点之间的连线 边可以有向，可以无向
图的概念
- 顶点表示图中的一个节点
- 边表示顶点和顶点之间的连线
- 相邻顶点，一条边连接在一起的顶点称为相邻顶点
- 度，相邻顶点的数量
- 路径，顶点v1,v2,…,vn的一个连续序列
- 简单路径，不包含重复的顶点
- 回路，第一个顶点和第二个顶点相同相同的路径
- 无向图，所有的边都没有方向
- 有向图，边有方向
- 无权图，边不携带权重
- 带权图，边有一定的权重
图的表示
- 邻接矩阵
邻接矩阵让每个节点和一个整数相关联，该整数作为数组的下标值，使用二维数组表示顶点之间的连接：
array[i][j] = 1表示两个顶点之间有边，否则array[i][j] = 0
在这里插入图片描述
邻接矩阵的问题：如果图是稀疏图，矩阵中会存在大量的0，浪费了空间
- 邻接表
由图中每个顶点以及和顶点相邻的顶点列表组成，这个列表用
数组、链表、字典、哈希表存储都可以
在这里插入图片描述
邻接表的问题：计算有向图的入度非常麻烦（入度：指向自己的数量，出度：指向别人的数量）
实现代码和思路
使用邻接表实现图
- 定义Graph类
- 定义vertexes数组存储顶点
- 定义edges字典存储邻列表
fucntion Graph() {
this.vertexes = []
this.edges = new Dictionary()
}添加顶点
- 顶点存储到数组
- 邻列表存储顶点及相邻的顶点,相邻的顶点构成数组
addVertex(v) {
this.vertexes.push(v)
this.edges.set(v, [])
}添加边
- 获取v1顶点对应的数组添加v2顶点
- 获取v2顶点对应的数组添加v1顶点
addEdge(v1,v2) {
this.edges.get(v1).push(v2)
this.edges.get(v2).push(v1)
}toString
- 遍历所有顶点，将顶点加入字符串
- 获取顶点对应的邻接表
- 遍历邻接表，将顶点加入字符串
- 每遍历完一个顶点对应的邻接表 换行
toString() {
let string = ''
for(let i = 0; i < this.vertexes.length; i++) {
string += this.edges.get(this.vertexes[i]) + '->'
let vEdges = this.edges.get(this.vertexes[i])
for(let j = 0; j < vEdges.length; j++) {
string += vEdges[j] + ''
}
string += '\n'
}
return string
}代码测试
let graph = new Graph()
let arr = ['A','B','C','D','E','F','G','H','I']
for (let i = 0; i < arr.length; i++) {
graph.addVertex(arr[i])
}
graph.addEdge('A', 'B')
graph.addEdge('A', 'C')
graph.addEdge('A', 'D')
graph.addEdge('C', 'D')
graph.addEdge('C', 'G')
graph.addEdge('D', 'G')
graph.addEdge('D', 'H')
graph.addEdge('B', 'E')
graph.addEdge('B', 'F')
graph.addEdge('E', 'I')
console.log(graph.toString())
在这里插入图片描述
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2021-04-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。