提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  Java

当前栏目

实现图

2023-02-18 16:30:13 时间

前言

图为非线性数据结构

图结构的特点

  • 一组顶点 用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())

相关文章